第四章 递归算法：从自我调用到问题分解
各位同学好，我是你们的老朋友。今天我们来聊聊递归——这个让很多初学者又爱又恨的话题。
说实话，我刚开始学C语言那会儿，看到递归也是一脸懵。什么？函数还能调用自己？这不死循环了吗？后来真正理解了，才发现递归其实是解决问题的一把利器。我在做嵌入式项目时，处理文件目录遍历、解析JSON树形结构，递归都是首选方案。
4.1 递归的定义与核心原理
递归，说白了就是「函数调用自身」。但这不是简单的重复，而是每次调用都把问题规模缩小一点，直到问题简单到可以直接解决。
你想想看，生活中就有很多递归的例子：
- 俄罗斯套娃——打开一个，里面还有一个更小的
- 照镜子——两面镜子对放，影像无限嵌套
- 数学中的阶乘——5! = 5 × 4!，而4! = 4 × 3!……
递归的核心原理就两条：
- 递推关系：大问题可以拆成小问题，且解法相同
- 终止条件：小到不能再小的时候，直接给出答案
重要理解：递归不是循环！每次递归调用都会在内存中开辟新的栈帧，保存当前函数的局部变量和返回地址。等最内层的调用返回后，再一层层「回溯」回来。
4.2 递归三要素
我教了这么多年C语言，总结出递归必须满足三个要素。少一个，你的递归就可能是错的：
| 要素 | 说明 | 反面案例 |
|---|---|---|
| 1. 明确终止条件 | 递归必须有一个「出口」，否则会无限递归导致栈溢出 | 忘记写if(base_case) return ... |
| 2. 问题规模递减 | 每次递归调用，参数必须朝着终止条件靠近 | factorial(n) 调用 factorial(n+1) —— 越调越大 |
| 3. 相同处理逻辑 | 子问题和原问题用同样的方法解决 | 递归函数内部突然换了算法 |
我的小技巧：写递归函数时，先写终止条件，再写递推关系。就像盖房子先打地基一样，终止条件就是递归的「地基」。
4.3 经典递归问题
4.3.1 阶乘——最朴素的递归
阶乘是递归的「Hello World」。数学定义本身就带有递归性质：
n! = n × (n-1)!，其中 0! = 1代码实现非常简单：
// 计算 n 的阶乘
unsigned long long factorial(int n) {
// 终止条件：0! = 1
if (n == 0) {
return 1;
}
// 递推关系：n! = n * (n-1)!
return n * factorial(n - 1);
}运行过程是什么样的？以 factorial(4) 为例：
factorial(4) → 4 * factorial(3)
→ 4 * (3 * factorial(2))
→ 4 * (3 * (2 * factorial(1)))
→ 4 * (3 * (2 * (1 * factorial(0))))
→ 4 * (3 * (2 * (1 * 1)))
→ 4 * (3 * (2 * 1))
→ 4 * (3 * 2)
→ 4 * 6
→ 24嗯，这里要注意：递归调用是「先递后归」。先一层层往下递，触底后再一层层往上归。我见过不少同学以为递归是边递边归，其实不是的。
4.3.2 斐波那契数列——递归的「双刃剑」
斐波那契数列的定义：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
直接翻译成递归：
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}代码看着很简洁对吧？但我要告诉你一个残酷的事实：这个实现效率极低。
为什么？因为存在大量重复计算。计算 fib(5) 时，fib(3) 被算了2次，fib(2) 被算了3次。随着 n 增大，计算量呈指数级增长。
我曾经踩过的坑：有一次在项目中用递归斐波那契算第50个数，程序直接卡死。后来一查，递归调用次数高达 2^50 量级，栈空间根本扛不住。所以，不是所有递归定义都适合用递归实现。
改进方案有两种：
- 记忆化递归：用一个数组缓存已经算过的值
- 迭代法：用循环代替递归，效率更高
4.3.3 汉诺塔——递归思维的巅峰
汉诺塔问题：有三根柱子A、B、C，A上有n个大小不同的圆盘，要把所有圆盘从A移到C，每次只能移动一个，且大盘不能压在小盘上。
这个问题用递归思考非常优雅：
void hanoi(int n, char from, char to, char aux) {
// 终止条件：只有一个盘子，直接移动
if (n == 1) {
printf("移动盘子 1 从 %c 到 %c\n", from, to);
return;
}
// 1. 先把上面 n-1 个盘子从 from 移到 aux
hanoi(n - 1, from, aux, to);
// 2. 把最大的盘子从 from 移到 to
printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
// 3. 再把 n-1 个盘子从 aux 移到 to
hanoi(n - 1, aux, to, from);
}你看，核心思路就三步：
- 把上面n-1个盘子「看成整体」移到辅助柱
- 把最底下的大盘子移到目标柱
- 再把n-1个盘子从辅助柱移到目标柱
这就是递归的精髓——相信你的函数能处理好子问题，你只需要关心当前这一步怎么走。
4.4 递归与迭代的对比
很多同学问我：「老师，递归和循环到底选哪个？」
我的回答是：看场景，没有绝对的优劣。下面这张表是我多年经验的总结：
| 对比维度 | 递归 | 迭代（循环） |
|---|---|---|
| 代码可读性 | 简洁，接近数学定义 | 需要维护循环变量，稍显啰嗦 |
| 内存消耗 | 每次调用占用栈空间，容易栈溢出 | 只占用固定内存 |
| 执行效率 | 函数调用有额外开销，较慢 | 直接跳转，效率高 |
| 适用场景 | 树形结构、分治算法、数学定义 | 线性遍历、累加累乘 |
| 调试难度 | 调用栈深，不易跟踪 | 单层循环，容易打断点 |
我的建议：
- 问题本身有递归结构（如树、图、分治）→ 用递归
- 问题简单线性，或对性能要求高 → 用迭代
- 递归深度超过1000层 → 考虑改迭代，或增大栈空间
4.5 本章知识体系总览
下面这张图，是我亲手画的递归知识框架，帮你理清思路：
4.6 避坑指南与经验总结
最后，分享几个我这些年积累的递归「避坑」经验：
- 一定要有终止条件——这听起来是废话，但我真见过有人写递归忘了写if判断，结果程序跑飞了
- 注意参数变化——每次递归调用，参数必须朝着终止条件变化。比如 n-1、n/2，不能原地踏步
- 小心栈溢出——递归深度超过几千层，程序大概率会崩。嵌入式开发中栈空间更小，尤其要注意
- 能用迭代就用迭代——如果递归深度不确定，或者对性能有要求，优先考虑迭代
我的一个小习惯：写递归函数时，我会先在注释里写下「终止条件是什么」「每次递归参数怎么变」。这样写出来的递归，基本不会出大问题。
好了，递归的内容就讲到这里。记住一句话：递归是一种思维方式，不是一种编程技巧。当你学会用递归的眼光看问题，很多复杂问题都会变得简单。