目录一.什么是递归1.递归的思想2.最简单的递归3.栈溢出4.递归的限制条件二.递归举例1.求n的阶乘2.递归的问题一.什么是递归递归是一种解决问题的方法简单理解就是函数自己调用自己1.递归的思想把一个大的复杂的问题层层转化为和原问题相似但是规模较小的子问题来求解直到问题不能再被拆分递归就结束了就像剥洋葱剥开一层还有一层直到剥完就没有了所谓递归思想就是大事化小小事化无。2.最简单的递归我们可以写出世界上最简单的递归#includestdio.h int main() { printf(change word\n); main(); return 0; }程序先是循环打印change word然后异常结束了并且提示我们栈溢出了。3.栈溢出当我们正常程序运行结束代码是0。所以如果递归使用不当就会产生栈溢出的现象。4.递归的限制条件递归在使用时必须满足两个条件(1)递归存在限制条件当满足这个限制条件时递归就不再继续。(2)每次调用后越来越接近这个限制条件不能死循环。二.递归举例1.求n的阶乘一个正整数的阶乘是所有小于及等于该数的正整数的积并且0的阶乘等于1。5的阶乘就是1×2×3×4×5我们可以推到出5的阶乘就是4的阶乘×5依次类推。n0时n! (n-1) !*nn0时n0。我们就可以这样实现代码Fac(int n) { if (n 0) return 1; else return Fac(n - 1) * n; } int main() { //1.求n的阶乘 int n 0; scanf(%d, n); int r Fac(n); printf(%d\n, r); return 0; }假设我们想求3的阶乘首先往Fac函数中传入这个数函数判断是不是为0如果是就返回1不是就返回Fac(n-1)*n也就是说想求出3的阶乘调用函数先求2的阶乘想求出2的阶乘调用函数先求出1的阶乘想求出1的阶乘调用函数先求出0的阶乘 0的阶乘等于1。当第一次调用时n3返回Fac(3-1)*3第二次调用n2 n ! 0 执行返回Fac(2-1)*2第三次调用n 1, n ! 0 执行返回Fac(1-1)*1第四次调用n0 返回1。下面是程序执行流程图片解析第四次返回一个1所以上一次调用函数的结果就是1然后返回1*11第三次返回1Fac 1, 返回1*2 2第二次返回2 Fac 2, 返回2*3 6第1次函数调用返回6把返回值传给r所以3的阶乘就是6递归结束。2.递归的问题在c语言中每次调用函数都在栈区开辟一块空间这块空间被称为函数栈帧函数不返回时函数对应的栈帧空间就一直被占用。函数如果存在递归每次调用自己都会开辟自己的栈帧空间直到递归不再继续开始回归才会逐层释放空间。所以如果采用函数递归的方式完成代码递归层次如果太深就会浪费太多空间可能会导致栈溢出。下面我们可以举个例子 求第n个斐波那契数斐波那契数列从第3项开始每一项都等于前两项之和例如1 1 2 3 5 8 13 21 34 55使用递归来实现时我们创造出Fib()函数当n小于2时return 1当n2时return Fib(n-1) Fib(n-2)int Fib(int n) { if (n 2) return 1; else return Fib(n - 1) Fib(n - 2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); return 0; }我们输入40程序卡顿一秒后才给出结果当我们输入50时光标一直在闪烁并且很长时间都没有给出结果。因为每增加一个数计算量就会成指数增加所以效率特别低。如果使用循环的方式来解决计算量就很小了int main() { int a1, b1, c1; int n 0; scanf(%d, n); for (int i 2; i n; i) { c a b; a b; b c; } printf(%d\n, c); return 0; }