递归：从原理到实战

递归是编程中优雅且经典的思想但也是C语言中的重难点。初学者刚接触时可能会觉得绕但只要理解了核心就不难了。一.递归是什么1.1 递归的定义在 C 语言中递归就是函数自己调用自己。核心思想把大型复杂问题层层转化为与原问题相似、但规模更小的子问题直到子问题无法拆分递归结束。一句话记忆递是递推下去归是回归回来1.2 实例#includestdio.h int main() { printf(haha\n); main();//自己调用自己 return 0; }上述代码仅用来演示不是为了解决问题。二.递归的两个必要限制条件1.存在限制条件满足时停止递归2.每次递归要越来越接近限制条件满足以上两点递归才能正常结束避免陷入死循环与栈溢出三.递归举例1.n的阶乘思路n!n*(n-1)!代码#includestdio.h //求阶乘 int Fact(int n) { if(n0) return 1; else return n*Fact(n-1);//自己调用自己 } int main() { int n0; scanf(%d,n); int retFact(n); printf(%d,ret); return 0; }2.顺序打印整数的每一步思路当n9时直接打印当n9时n%10得到最后一位n/10去除最后一位利用递归先打印高位再打印低位代码#includestdio.h void print(int m) { if (m 9) { print(m / 10); } printf(%d ,m%10); } int main() { int n 0; scanf(%d, n); print(n); return 0; }3.打印斐波那契数思路Fib(n-1)Fib(n-2)代码#includestdio.h int Fib(int i) { if (i 2) return 1; else return Fib(i - 1) Fib(i - 2); } int main() { int n 0;//n代表求哪个斐波那契数 scanf(%d,n); int fib Fib(n); fib Fib(n); printf(%d, fib); return 0; }此代码虽然好理解写出来也简单但是当我们要求第50个的时候就会发现电脑会出现卡顿因为计算量实在太大我下面换一种思路不用递归#includestdio.h int Fib(int i) { int a 1; int b 1; int c 1; while (i 2) { c a b; a b; b c; i--; } return c; } int main() { int n 0;//n代表求哪个斐波那契数 scanf_s(%d,n); int fib Fib(n); fib Fib(n); printf(%d\n, fib); return 0; }以上是迭代循环四.递归和迭代的区别和优缺点简单理解版递归迭代优点代码简洁、逻辑直观适合树形结构、分治类问题效率高、无栈开销适合数值计算缺点函数调用有开销占用栈空间层次过深易栈溢出可能出现大量重复计算代码不如递归简洁区别函数自己调用自己用while/for循环反复执行五.递归使用建议优先写递归出口再写递推逻辑递归简洁且高效 → 用递归重复计算多、层次深 → 改用迭代 / 循环避免无节制递归防止栈溢出