10_函数递归_从阶乘到递归调用栈

函数递归从阶乘到递归调用栈一、本篇文章要解决什么问题上一篇学了函数——函数可以调用别的函数。那函数能不能调用自己能这就是递归。递归是 C 语言中非常有特色的一种编程技巧很多数据结构树、图和算法分治、回溯都依赖递归。但对初学者来说递归最大的困难是想不清楚执行过程。这篇文章帮你搞定三件事递归到底是什么——为什么函数可以调用自己而不乱套递归的两个核心条件递归出口什么时候停 递归关系怎么把大问题变小递归调用栈是怎么回事——帮你从底层理解递和归的过程二、先用一个简单例子理解2.1 套娃的故事俄罗斯套娃打开一个娃娃里面还有一个娃娃再打开还有一个……直到最小的那个打不开了。递一层一层打开——把大问题拆成小问题归一层一层合上——小问题解决了大问题自然有答案递归就是自己调用自己但每次调用时参数在变小或向终止条件靠近最终到达一个最小问题可以直接解决不需要再调用自己。2.2 递归和循环的关系递归能做的事循环也能做反之亦然。区别在于表达方式循环告诉计算机怎么做步骤递归告诉计算机问题是什么定义有些场景用递归表达更自然如树形结构遍历有些场景用循环更高效。初学者先要理解递归的思想再根据场景选择。三、核心知识点讲解3.1 递归的两个必要元素任何一个递归函数必须包含两部分递归出口终止条件什么情况下不继续递归直接返回答案递归关系怎么把规模为 n 的问题转化为规模为 n-1或更小的问题没有出口 无限递归 栈溢出程序崩溃。3.2 阶乘——最经典的递归入门阶乘定义n! 1 × 2 × 3 × ... × n。但用递归思想看n! n × (n-1)! 0! 1 ← 递归出口0 的阶乘定义为 1#includestdio.hintfactorial(intn){if(n0)// 非法输入负数没有阶乘{return-1;// 返回 -1 表示错误调用前应先检查 n}if(n0||n1)// 递归出口0! 1, 1! 1{return1;}returnn*factorial(n-1);// 递归关系}intmain(void){printf(5! %d\n,factorial(5));printf(0! %d\n,factorial(0));// printf(-3! %d\n, factorial(-3)); // 建议在调用前检查不传入负数return0;}运行结果5! 120 0! 1图10-1 阶乘递归展开图图解 factorial(5) 的完整递进和回溯过程。图10-2 递归调用栈示意图从内存角度解释递归的栈本质和栈溢出的风险。3.3 递归调用栈——递和归的详细过程以factorial(5)为例递一层层进入 factorial(5) → 5 * factorial(4) → 4 * factorial(3) → 3 * factorial(2) → 2 * factorial(1) → return 1 ← 到达出口 归一层层返回 ← return 1 ← return 2 * 1 2 ← return 3 * 2 6 ← return 4 * 6 24 ← return 5 * 24 120每次调用factorial都会在调用栈上创建一个新的栈帧保存该层调用的局部变量这里是n和返回位置。当到达出口后栈帧逐个销毁返回值逐层传回。如果递归太深比如factorial(100000)栈空间不够用就发生栈溢出Stack Overflow。3.4 斐波那契数列——递归的双分支斐波那契F(1) 1, F(2) 1, F(n) F(n-1) F(n-2)#includestdio.hintfibonacci(intn){if(n1||n2)// 递归出口两个终止条件{return1;}returnfibonacci(n-1)fibonacci(n-2);// 两个递归调用}intmain(void){for(inti1;i10;i){printf(%d ,fibonacci(i));}printf(\n);return0;}运行结果1 1 2 3 5 8 13 21 34 55效率问题fibonacci(5)会调用fibonacci(4)和fibonacci(3)而fibonacci(4)又会调用fibonacci(3)——重复计算了大量子问题。这是斐波那契递归实现的最大缺点也是为什么面试里常被问到优化方案。图10-3 斐波那契递归重复计算图直观展示为什么斐波那契递归效率低。四、完整代码示例一个递归思想的实用案例——递归打印一个整数按位拆分的结果#includestdio.h// 递归打印整数的每一位voidprintDigits(intn){if(n10)// 递归出口只剩一位{printf(%d ,n);return;}printDigits(n/10);// 先递归打印高位printf(%d ,n%10);// 再打印当前最低位}// 循环版本用于对比voidprintDigitsLoop(intn){// 先处理逆序问题把每一位存到数组再倒序输出intdigits[10];intcount0;while(n0){digits[count]n%10;n/10;}for(inticount-1;i0;i--){printf(%d ,digits[i]);}}intmain(void){intnum12345;printf(数字%d\n,num);printf(递归打印);printDigits(num);printf(\n);printf(循环打印);printDigitsLoop(num);printf(\n);// 演示 10 以内数字直接触发出口printf(\n数字 7 递归打印);printDigits(7);printf(\n);// 注意当前 printDigits 主要面向正整数。输入 0 会输出 0因 n10 成立// 输入负数则 n%10 的结果与具体实现有关建议调用前检查参数。return0;}五、运行结果数字12345 递归打印1 2 3 4 5 循环打印1 2 3 4 5 数字 7 递归打印7六、代码逐行解析递归打印的核心逻辑voidprintDigits(intn){if(n10)// 递归出口{printf(%d ,n);return;}printDigits(n/10);// 先递归处理高位printf(%d ,n%10);// 再打印当前最低位}执行过程以 n123 为例printDigits(123) → if (123 10) 不成立 → printDigits(12) ← 递先处理高位 → if (12 10) 不成立 → printDigits(1) ← 再递只剩最高位 → if (1 10) 成立 → printf(1) → return → printf(2) ← 归打印当前位 → printf(3) ← 归打印当前位关键点printDigits(n/10)调用之后的代码在归阶段才执行。这就是递归的顺序控制能力——先处理深层问题再回溯处理本层问题。用循环实现这个效果需要额外用数组倒序代码远不如递归简洁。七、初学者常见错误错误1缺少递归出口——无限递归// 错误写法——没有出口intfactorial(intn){returnn*factorial(n-1);// n 越来越小但永远不会停}// 结果栈溢出Stack Overflow程序崩溃错误2递归出口的条件覆盖面不够// 错误写法——n1 有出口n0 会无限递归intfactorial(intn){if(n1)return1;returnn*factorial(n-1);}// factorial(0) → factorial(-1) → ... 无限递归// 正确if (n 1) return 1;错误3递归参数没有向出口靠近// 错误写法——参数不变永远到不了出口voidbadRecursion(intn){if(n0)return;badRecursion(n);// 应该传 n-1}错误4大规模斐波那契递归卡死printf(%d\n,fibonacci(50));// 极慢计算量指数级增长// 要么用循环实现要么用记忆化缓存中间结果错误5在递归函数里用 static 变量累积结果// 这种写法虽然可能通过但破坏了递归的纯粹性第二次调用就有残留值intfactorial(intn){staticintresult1;// 不推荐}八、练习题练习题1递归求和用递归实现一个函数int sum(int n)返回 12…n 的值。在 main 中测试sum(100)。提示递归关系sum(n) n sum(n-1)出口sum(1) 1。练习题2递归反转字符串用递归实现一个函数将用户输入的字符串反转输出只输出不修改原数组。提示先输出最后一个字符再递归处理前面的子串。出口字符串长度为 0 或 1。练习题3汉诺塔问题选做阅读汉诺塔问题的描述用递归输出将 n 个盘子从 A 柱移到 C 柱的步骤每次只能移一个盘子且大盘不能放在小盘上面。这是递归思想的经典问题n3 时应有 7 步。九、本篇总结递归 函数调用自己必须包含递归出口和递归关系两个要素缺少出口 无限递归 栈溢出这是递归最严重的错误递是压栈过程问题缩小归是出栈过程答案合并斐波那契递归实现效率低——重复计算太多用循环或记忆化优化递归和循环可以互相转换选择让代码更清晰的写法图10-4 递归打印数字的递/归过程图帮助理解递归调用之后的代码在归阶段执行这一核心概念。