一、递归思想：从“自己调用自己”说起
递归这东西，我刚入行时觉得挺玄乎的。说白了，就是一个函数调用它自己。你想想看，这听起来像不像俄罗斯套娃？一个大娃娃里面套着一个小娃娃，小娃娃里面再套一个更小的……直到套到最小的那个为止。
递归的核心就两件事：递推关系和终止条件。递推关系告诉你“怎么拆”，终止条件告诉你“拆到什么时候停”。
递归三要素：
- 明确函数功能——这个函数到底要干什么？
- 寻找递归结束条件——什么时候不再调用自己？
- 找出等价关系式——如何把大问题拆成小问题？
我在项目中遇到过不少新手，一上来就写递归，结果栈溢出了还不知道怎么回事。嗯，这里要注意：递归不是万能的，每次函数调用都会消耗栈空间，深度太大就会崩。
一个简单的例子：阶乘
// 递归计算 n!
int factorial(int n) {
// 终止条件：0! = 1
if (n == 0) return 1;
// 递推关系：n! = n * (n-1)!
return n * factorial(n - 1);
}你看，这个代码很简洁。但简洁不等于高效。每次调用都要压栈、传参、返回，开销不小。我建议你在递归深度可控（比如不超过几百层）的情况下再用。
我的习惯：写递归前先估算一下最大深度。如果深度超过 1000，我会优先考虑改成迭代。
二、分治策略：把大问题拆成小问题
分治，说白了就是“分而治之”。你遇到一个复杂问题，别急着硬刚，先看看能不能拆成几个独立的子问题。每个子问题解决了，合起来就是答案。
分治的套路很固定：
- 分解——把原问题拆成若干个规模更小的子问题
- 解决——递归地解决每个子问题
- 合并——把子问题的解合并成原问题的解
我做过一个图像处理的项目，需要把一张大图做边缘检测。直接处理整张图，内存吃不消。后来我用分治：把图切成 16 块，每块单独处理，最后拼回去。效果一样，内存占用降了 70%。
注意：分治的前提是子问题之间相互独立。如果子问题有重叠，分治反而会做大量重复计算。这时候该用动态规划，别硬套分治。
三、汉诺塔问题：分治的经典案例
汉诺塔问题，你肯定听说过。三根柱子，一堆盘子，要把所有盘子从 A 移到 C，每次只能移一个，大盘不能压小盘。
这个问题用递归来解，思路特别清晰：
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("移动盘子 1 从 %c 到 %c\n", from, to);
return;
}
// 先把上面 n-1 个盘子从 from 移到 aux
hanoi(n - 1, from, aux, to);
// 再把最下面的盘子从 from 移到 to
printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
// 最后把 n-1 个盘子从 aux 移到 to
hanoi(n - 1, aux, to, from);
}你看，代码就这么几行。但它的时间复杂度是 O(2ⁿ)，盘子一多就完蛋。我记得有一次面试，面试官让我手写汉诺塔，我写出来了，他接着问“64 个盘子需要多少步？”我算了一下：2⁶⁴ - 1，约 1.8×10¹⁹ 步。按每秒移一个算，要 5800 亿年……嗯，宇宙都没那么老。
分治思想在汉诺塔中的体现：
- 分解：把 n 个盘子的问题拆成 2 个 n-1 盘子的问题
- 解决：递归处理 n-1 个盘子的移动
- 合并：把两次移动的结果拼起来
四、斐波那契数列优化：从指数级到线性级
斐波那契数列，教科书上最爱用的递归例子：
// 最朴素的递归——慢到让你怀疑人生
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}这段代码，n=40 的时候就已经卡得不行了。为什么会这样？因为它在疯狂重复计算。你算一下 fib(5)，它要算 fib(4) 和 fib(3)；算 fib(4) 又要算 fib(3) 和 fib(2)……fib(3) 被算了两次。n 越大，重复越严重，时间复杂度是 O(2ⁿ)。
我曾经在一个嵌入式项目里需要快速计算斐波那契数，用这个递归版本，单片机直接死机了。后来我换了两种优化方式：
优化方案一：记忆化递归（自顶向下）
// 用一个数组缓存已经算过的结果
int fib_memo(int n, int* memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // 查缓存
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
return memo[n];
}这样每个 n 只算一次，时间复杂度降到 O(n)，空间复杂度 O(n)。
优化方案二：迭代法（自底向上）
// 不用递归，用循环
int fib_iter(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}这个更狠，时间复杂度 O(n)，空间复杂度 O(1)。在嵌入式环境里，我基本都用这个版本。你想想看，同样的功能，一个版本让单片机死机，另一个版本跑得飞起——这就是优化的价值。
我的建议：遇到递归问题时，先问自己三个问题——
- 递归深度会不会太大？
- 有没有重复计算？
- 能不能改成迭代？
这三个问题想清楚了，你就能避免很多坑。
五、知识体系总览
下面这张图，把本章的核心内容串起来了。你可以把它当作一张地图，随时回来看看。
六、本章小结
递归和分治，是算法设计里最基础也最实用的思想。你掌握了它们，很多看似复杂的问题都能迎刃而解。
我个人习惯是：先想能不能分治，再想能不能递归，最后想能不能优化。这个顺序帮我避开了不少坑。
记住几个关键点：
- 递归一定要有终止条件，否则栈溢出
- 分治的子问题要相互独立，否则考虑动态规划
- 斐波那契这种有大量重复计算的，别用朴素递归
- 嵌入式环境里，优先考虑迭代而非递归
好了，这一章就到这里。代码不多，但思想很重要。你把这些想透了，后面的排序、查找、树、图，学起来都会轻松很多。
公众号:蓝海资料掘金营，微信deep3321