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

函数递归：从阶乘到递归调用栈

一、本篇文章要解决什么问题

上一篇学了函数——函数可以调用别的函数。那函数能不能调用自己？能，这就是递归。

递归是 C 语言中非常有特色的一种编程技巧，很多数据结构（树、图）和算法（分治、回溯）都依赖递归。但对初学者来说，递归最大的困难是"想不清楚执行过程"。

这篇文章帮你搞定三件事：

1. 递归到底是什么——为什么函数可以调用自己而不乱套
2. 递归的两个核心条件：递归出口（什么时候停）+ 递归关系（怎么把大问题变小）
3. 递归调用栈是怎么回事——帮你从底层理解"递"和"归"的过程

二、先用一个简单例子理解

2.1 套娃的故事

俄罗斯套娃：打开一个娃娃，里面还有一个娃娃，再打开还有一个……直到最小的那个打不开了。

递：一层一层打开——把大问题拆成小问题

归：一层一层合上——小问题解决了，大问题自然有答案

递归就是"自己调用自己"，但每次调用时参数在变小（或向终止条件靠近），最终到达一个"最小问题"可以直接解决，不需要再调用自己。

2.2 递归和循环的关系

递归能做的事，循环也能做（反之亦然）。区别在于表达方式：

• 循环：告诉计算机"怎么做"（步骤）
• 递归：告诉计算机"问题是什么"（定义）

有些场景用递归表达更自然（如树形结构遍历），有些场景用循环更高效。初学者先要理解递归的思想，再根据场景选择。

三、核心知识点讲解

3.1 递归的两个必要元素

任何一个递归函数必须包含两部分：

1. 递归出口（终止条件）：什么情况下不继续递归，直接返回答案
2. 递归关系：怎么把规模为 n 的问题转化为规模为 n-1（或更小）的问题

没有出口 = 无限递归 = 栈溢出（程序崩溃）。

3.2 阶乘——最经典的递归入门

阶乘定义：n! = 1 × 2 × 3 × ... × n。但用递归思想看：

n! = n × (n-1)! 0! = 1 ← 递归出口（0 的阶乘定义为 1）

#include<stdio.h>intfactorial(intn){if(n<0)// 非法输入：负数没有阶乘{return-1;// 返回 -1 表示错误（调用前应先检查 n）}if(n==0||n==1)// 递归出口：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)

#include<stdio.h>intfibonacci(intn){if(n==1||n==2)// 递归出口：两个终止条件{return1;}returnfibonacci(n-1)+fibonacci(n-2);// 两个递归调用}intmain(void){for(inti=1;i<=10;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 斐波那契递归重复计算图：直观展示为什么斐波那契递归效率低。

四、完整代码示例

一个递归思想的实用案例——递归打印一个整数按位拆分的结果：

#include<stdio.h>// 递归打印整数的每一位voidprintDigits(intn){if(n<10)// 递归出口：只剩一位{printf("%d ",n);return;}printDigits(n/10);// 先递归打印高位printf("%d ",n%10);// 再打印当前最低位}// 循环版本（用于对比）voidprintDigitsLoop(intn){// 先处理逆序问题：把每一位存到数组再倒序输出intdigits[10];intcount=0;while(n>0){digits[count++]=n%10;n/=10;}for(inti=count-1;i>=0;i--){printf("%d ",digits[i]);}}intmain(void){intnum=12345;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"（因 n<10 成立），// 输入负数则 n%10 的结果与具体实现有关，建议调用前检查参数。return0;}

五、运行结果

数字：12345 递归打印：1 2 3 4 5 循环打印：1 2 3 4 5 数字 7 递归打印：7

六、代码逐行解析

递归打印的核心逻辑：

voidprintDigits(intn){if(n<10)// 递归出口{printf("%d ",n);return;}printDigits(n/10);// 先递归处理高位printf("%d ",n%10);// 再打印当前最低位}

执行过程（以 n=123 为例）：

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：递归出口的条件覆盖面不够

// 错误写法——n=1 有出口，n=0 会无限递归intfactorial(intn){if(n==1)return1;returnn*factorial(n-1);}// factorial(0) → factorial(-1) → ... 无限递归// 正确：if (n <= 1) return 1;

错误3：递归参数没有向出口靠近

// 错误写法——参数不变，永远到不了出口voidbadRecursion(intn){if(n==0)return;badRecursion(n);// 应该传 n-1！}

错误4：大规模斐波那契递归卡死

printf("%d\n",fibonacci(50));// 极慢！计算量指数级增长// 要么用循环实现，要么用"记忆化"缓存中间结果

错误5：在递归函数里用 static 变量累积结果

// 这种写法虽然可能通过，但破坏了递归的纯粹性，第二次调用就有残留值intfactorial(intn){staticintresult=1;// 不推荐}

八、练习题

练习题1：递归求和

用递归实现一个函数int sum(int n)，返回 1+2+…+n 的值。在 main 中测试sum(100)。

提示：递归关系：sum(n) = n + sum(n-1)，出口：sum(1) = 1。

练习题2：递归反转字符串

用递归实现一个函数，将用户输入的字符串反转输出（只输出，不修改原数组）。

提示：先输出最后一个字符，再递归处理前面的子串。出口：字符串长度为 0 或 1。

练习题3：汉诺塔问题（选做）

阅读汉诺塔问题的描述，用递归输出将 n 个盘子从 A 柱移到 C 柱的步骤（每次只能移一个盘子，且大盘不能放在小盘上面）。这是递归思想的经典问题，n=3 时应有 7 步。

九、本篇总结

1. 递归 = 函数调用自己，必须包含递归出口和递归关系两个要素
2. 缺少出口 = 无限递归 = 栈溢出，这是递归最严重的错误
3. "递"是压栈过程（问题缩小），"归"是出栈过程（答案合并）
4. 斐波那契递归实现效率低——重复计算太多，用循环或记忆化优化
5. 递归和循环可以互相转换，选择让代码更清晰的写法

图10-4 递归打印数字的递/归过程图：帮助理解"递归调用之后的代码在归阶段执行"这一核心概念。