一、递归初探：什么是递归？

递归这个词，听起来挺唬人的。

我第一次接触递归时，翻了好几页书，越看越懵。后来在项目里真正用上了，才恍然大悟——说白了，递归就是「自己调用自己」。

你想想看，一个函数在它的函数体里，又调用了它自己。这听起来像不像俄罗斯套娃？打开一个，里面还有一个，再打开，还有……直到最后那个最小的，不能再打开了。

递归也是这个道理。

生活中的递归

举个简单的例子。你站在两排人中间，想知道自己排在第几位。你没法一眼看到头，怎么办？

你拍了拍前面的人，问他：「兄弟，你前面还有几个人？」

他也不知道，于是他又拍了拍他前面的人……

一直问到最前面那个人，他说：「我前面没人了，我是第1个。」

然后这个信息再一层层传回来：第1个告诉第2个，第2个告诉第3个……最后传到你这里，你就知道了自己的位置。

这就是递归的完整过程。

递归的三大要素

我在项目中写递归时，总结出三个必须想清楚的点。少了任何一个，递归就会出问题。

1. 基线条件（Base Case）

基线条件，就是递归的「出口」。没有它，递归会无限循环下去，直到栈溢出。

刚才排队那个例子，最前面那个人说「我前面没人了」——这就是基线条件。

写代码时，基线条件通常是一个可以直接返回结果的简单情况，不需要再递归。

2. 递归前进（Recursive Step）

递归前进，就是让问题规模逐步缩小的那一步。

每次递归调用，都要朝着基线条件靠近一步。如果每次调用问题规模不变，那就永远到不了基线条件。

比如求阶乘，n! 依赖 (n-1)!，这就是在缩小问题规模。

3. 递归返回（Return）

递归返回，就是把子问题的结果组合起来，得到原问题的答案。

还是排队那个例子：前面的人把他的位置数告诉你，你在这个数上加1，就是你的位置。这个「加1」就是递归返回时的操作。

用阶乘例子，写出第一个递归函数

阶乘是递归的「Hello World」。几乎所有教材都用它举例，因为它足够简单，又能把递归的三大要素都体现出来。

阶乘的定义：

• 0! = 1
• n! = n × (n-1)!

你看，这个定义本身就是递归的。n! 依赖 (n-1)!，而 (n-1)! 又依赖 (n-2)!……直到 0! = 1。

下面是我写的阶乘递归函数：

#include <stdio.h>

// 递归求阶乘
int factorial(int n) {
    // 基线条件：n 为 0 或 1 时，直接返回 1
    if (n <= 1) {
        return 1;
    }
    
    // 递归前进：问题规模缩小，调用 factorial(n-1)
    // 递归返回：n 乘以子问题的结果
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    int result = factorial(num);
    printf("%d! = %d\n", num, result);
    return 0;
}

运行结果：

5! = 120

代码拆解

我们一行行来看这个函数。

基线条件：

if (n <= 1) {
    return 1;
}

当 n 是 0 或 1 时，阶乘结果是 1。这是递归的出口，不再继续调用自己。

递归前进：

factorial(n - 1)

每次调用，n 都减 1。从 5 到 4，再到 3、2、1……一步步靠近基线条件。

递归返回：

return n * factorial(n - 1);

子问题 factorial(n-1) 的结果算出来后，乘以 n，就是当前问题的结果。

递归的执行过程

我建议你手动走一遍这个流程，对理解递归很有帮助。

调用 factorial(5) 时，实际发生的事情是这样的：

factorial(5) = 5 * factorial(4)
            = 5 * (4 * factorial(3))
            = 5 * (4 * (3 * factorial(2)))
            = 5 * (4 * (3 * (2 * factorial(1))))
            = 5 * (4 * (3 * (2 * 1)))
            = 5 * (4 * (3 * 2))
            = 5 * (4 * 6)
            = 5 * 24
            = 120

看到了吗？递归先一层层「递」下去，直到碰到基线条件。然后一层层「归」回来，把结果组合起来。

递归的流程图

下面这张图，展示了 factorial(5) 的完整递归过程。你可以对照着代码看，会更清晰。

写递归时要注意什么

嗯，这里有几个我踩过的坑，分享给你。

1. 一定要有基线条件

没有基线条件的递归，就是死循环。程序会一直往栈里压入函数调用，直到栈空间耗尽，程序崩溃。

2. 确保每次递归都向基线条件靠近

如果递归调用时问题规模没有缩小，那就永远到不了基线条件。

阶乘的例子中，每次调用 n-1，就是在缩小规模。如果你不小心写成了 n+1，那就离基线条件越来越远了。

3. 递归深度不要太大

递归调用会占用栈空间。每调用一次，就在栈上分配一块内存。如果递归深度太大（比如几万层），栈空间会不够用。

一般来说，递归深度控制在几百层以内比较安全。如果深度可能很大，建议改用循环实现。

递归 vs 循环

阶乘用循环也能写，而且效率更高：

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

那为什么还要学递归？

因为有些问题，用循环写起来很痛苦，用递归却非常自然。比如：

• 遍历树形结构（文件目录、DOM树）
• 分治算法（快速排序、归并排序）
• 回溯算法（八皇后、迷宫寻路）

这些场景下，递归的代码更简洁、更易读。说白了，递归是思维层面的简化，循环是执行层面的优化。

小结

这一章我们聊了：

• 递归是什么——自己调用自己
• 递归的三大要素——基线条件、递归前进、递归返回
• 用阶乘例子写出了第一个递归函数
• 递归的执行过程——先递后归
• 写递归时的注意事项

递归的思想其实不复杂。你想想看，就是把一个大问题拆成小问题，小问题再拆成更小的问题……直到拆到不能再拆为止。然后从最小的那个问题开始，一步步往回推，得到最终答案。

下一章，我们会用更多的例子来巩固递归思想。到时候你会发现，递归其实挺有意思的。

---