第27讲 递归与分治：递归的基本概念与实现、分治法的基本思想、典型问题
各位同学，今天我们来聊聊递归和分治。这两个概念，说白了就是程序员的「左右互搏术」。我自己刚入行时，总觉得递归很玄乎，直到亲手调过几次栈溢出，才真正理解了它的脾气。
一、递归的基本概念
递归，就是函数调用自己。嗯，听起来有点绕。但你想啊，生活中也有递归：俄罗斯套娃、镜子里的镜子、还有你妈让你叫你妈吃饭……
在C语言里，递归函数长这样：
// 计算阶乘：n!
int factorial(int n) {
if (n <= 1) {
return 1; // 递归终止条件
}
return n * factorial(n - 1); // 递归调用
}这里有两个关键点：
- 递归终止条件：没有它，函数会无限调用下去，直到栈溢出。我见过太多新手忘了写这个，然后一脸懵地看着程序崩溃。
- 递归调用：每次调用都向终止条件靠近一步。
核心要点：递归的本质是「将大问题拆成小问题，小问题再拆成更小的问题，直到问题简单到可以直接解决」。
二、递归的实现细节
递归在底层是怎么工作的？靠的是函数调用栈。每次递归调用，系统都会把当前函数的局部变量、返回地址等信息压入栈中。等递归返回时，再依次弹出。
我给大家画个图，看看递归调用栈长什么样：
避坑指南：我曾经在项目中用递归处理一个深度很大的树结构，结果栈溢出了。后来改成迭代+显式栈才搞定。记住：递归深度超过1000层就要小心了，Windows默认栈大小只有1MB。
三、分治法的基本思想
分治法，说白了就是「分而治之」。把一个大问题拆成几个小问题，分别解决，再把结果合并起来。
分治法的三个步骤：
- 分解：将原问题分解成若干个规模较小的子问题
- 解决：递归地解决这些子问题
- 合并：将子问题的解合并成原问题的解
你想想看，这和递归是不是天生一对？分治法的实现几乎总是用递归。我习惯把分治法看作「递归的应用框架」。
四、典型问题1：汉诺塔
汉诺塔问题，是递归入门的经典。三根柱子，一堆盘子，要把所有盘子从A移到C，每次只能移一个，大盘不能压小盘。
代码实现：
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("移动盘子 1 从 %c 到 %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to); // 把上面n-1个盘子移到辅助柱
printf("移动盘子 %d 从 %c 到 %c\n", n, from, to); // 移动最下面的盘子
hanoi(n - 1, aux, to, from); // 把n-1个盘子从辅助柱移到目标柱
}这个代码只有5行，但背后是2ⁿ-1步操作。我记得第一次看到这个解法时，觉得太巧妙了——你根本不需要关心每一步具体怎么移，只需要相信递归能帮你搞定。
注意：汉诺塔的时间复杂度是O(2ⁿ)，n稍微大一点（比如n=30）就需要跑很久。我在面试中遇到过候选人写汉诺塔，然后问「n=64要多久」，答案是约5849亿年——嗯，宇宙都等不了。
五、典型问题2：全排列
全排列问题：给定一个数组，输出所有可能的排列方式。
思路：固定第一个位置，然后递归排列剩下的元素。
void permute(int arr[], int start, int end) {
if (start == end) {
// 打印当前排列
for (int i = 0; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for (int i = start; i <= end; i++) {
swap(&arr[start], &arr[i]); // 交换
permute(arr, start + 1, end); // 递归排列剩余部分
swap(&arr[start], &arr[i]); // 回溯，恢复原状
}
}这里有个小技巧：回溯。交换后递归，递归完再换回来。我刚开始写全排列时，忘了回溯这一步，结果排列出来的结果全是乱的。嗯，调试了半小时才发现。
六、典型问题3：棋盘覆盖
棋盘覆盖问题：一个2ⁿ×2ⁿ的棋盘，有一个格子是特殊方格，要用L型骨牌覆盖所有格子。
分治思路：
- 把棋盘分成4个2ⁿ⁻¹×2ⁿ⁻¹的小棋盘
- 特殊方格在其中一个子棋盘里
- 在其他三个子棋盘的交界处放一个L型骨牌，制造出三个「虚拟特殊方格」
- 递归处理四个子棋盘
代码实现（核心部分）：
void chessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
int s = size / 2;
int t = ++tile; // L型骨牌编号
// 处理左上角子棋盘
if (dr < tr + s && dc < tc + s) {
chessBoard(tr, tc, dr, dc, s);
} else {
board[tr + s - 1][tc + s - 1] = t;
chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 处理右上角子棋盘
if (dr < tr + s && dc >= tc + s) {
chessBoard(tr, tc + s, dr, dc, s);
} else {
board[tr + s - 1][tc + s] = t;
chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
// 处理左下角子棋盘
if (dr >= tr + s && dc < tc + s) {
chessBoard(tr + s, tc, dr, dc, s);
} else {
board[tr + s][tc + s - 1] = t;
chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
// 处理右下角子棋盘
if (dr >= tr + s && dc >= tc + s) {
chessBoard(tr + s, tc + s, dr, dc, s);
} else {
board[tr + s][tc + s] = t;
chessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}这个问题的巧妙之处在于：你不需要知道特殊方格具体在哪，只需要保证每个子棋盘都有一个「特殊方格」即可。分治法的精髓就在这里——把复杂问题拆成结构相同的子问题。
七、递归与分治的对比总结
| 维度 | 递归 | 分治法 |
|---|---|---|
| 定义 | 函数调用自身的编程技巧 | 将问题分解为子问题求解的算法思想 |
| 关系 | 分治法通常用递归实现 | 递归是分治法的实现工具 |
| 典型应用 | 汉诺塔、斐波那契、树遍历 | 归并排序、快速排序、棋盘覆盖 |
| 注意事项 | 防止栈溢出，注意终止条件 | 子问题要独立，合并操作要高效 |
我的建议：初学者先练递归，把「函数调用自己」这个思维模式刻进脑子里。然后再学分治法，你会发现很多算法问题都可以用「分治三步走」来拆解。我个人习惯在写递归函数前，先在纸上画出递归树，这样不容易出错。
好了，这一讲的内容就到这里。递归和分治是算法大厦的基石，值得你花时间好好消化。下一讲我们会继续深入，看看分治法在排序和查找中的精彩应用。