递归思想与函数调用栈

Kingcq2026/7/11大约 8 分钟

引入：把大问题拆成小问题

前面我们写的函数都是“直线式”执行的：调用一个函数，它做完自己的事，返回结果，然后继续往下走。但有一类问题，解决它的思路和解决一个更小的同类问题一模一样。比如算 5 的阶乘，其实只需要知道 4 的阶乘再乘 5；算 4 的阶乘，又只需要知道 3 的阶乘。

这种“自己调用自己”的编程技巧就叫递归。它看起来很玄，但理解之后非常强大。

学习目标

理解递归的定义和思想。
掌握递归三要素：终止条件、递归关系、向终止条件收敛。
理解函数调用栈的执行过程。
能比较递归与循环的优劣。
知道递归可能带来的栈溢出风险。

什么是递归

递归就是函数在执行过程中直接或间接调用自身。一个完整的递归必须满足两个条件：

存在终止条件：不能无限调用下去，否则程序会崩溃。
每次调用都向终止条件靠近：问题规模越来越小，最终能停下来。

生活中的递归

俄罗斯套娃就是递归的直观例子：每个娃娃里面都有一个更小的、和自己一样的娃娃，直到最小的那个娃娃不能再拆为止。

递归三要素

写递归函数时，我建议你按下面三个要素来思考：

1. 终止条件（Base Case）

递归到什么时候停止？这是最容易遗漏也最致命的部分。没有终止条件，函数会无限调用自己，直到栈空间耗尽。

2. 递归关系（Recurrence Relation）

当前问题如何转化为一个规模更小的相同问题？比如 n! = n × (n-1)!。

3. 向终止条件收敛

每次递归调用，问题的规模都要比上一次小。否则就会像跑步机一样原地踏步，永远到不了终点。

经典例子一：阶乘

数学定义

n! = n × (n-1) × (n-2) × ... × 1
0! = 1

也可以写成递归形式：

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

代码实现

#include <stdio.h>

long long factorial(int n) {
    if (n == 0) {          // 终止条件
        return 1;
    }
    return n * factorial(n - 1);  // 递归关系，n 越来越小
}

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

输出：

5! = 120

函数调用栈的执行过程

要真正理解递归，必须理解函数调用栈（call stack）。

每次函数调用时，系统会在栈上分配一块空间，叫做栈帧，用来保存这个函数的参数、局部变量和返回地址。当函数执行完毕，这块栈帧就被弹出，控制权回到调用它的地方。

以 factorial(5) 为例，调用过程是：

factorial(5)
    → factorial(4)
        → factorial(3)
            → factorial(2)
                → factorial(1)
                    → factorial(0) 返回 1
                ← 返回 1
            ← 返回 2
        ← 返回 6
    ← 返回 24
← 返回 120

每一层调用都会压入一个新的栈帧，直到最底层返回，然后逐层回代计算结果。

栈帧不会共享

每一层递归调用的局部变量都是独立的。比如 factorial(5) 和 factorial(4) 里的 n 分别是 5 和 4，互不影响。

经典例子二：斐波那契数列

斐波那契数列的定义非常自然地适合递归：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

代码实现

#include <stdio.h>

long long fibonacci(int n) {
    if (n == 0) return 0;  // 终止条件 1
    if (n == 1) return 1;  // 终止条件 2
    return fibonacci(n - 1) + fibonacci(n - 2);  // 递归关系
}

int main(void) {
    int n = 10;
    printf("F(%d) = %lld\n", n, fibonacci(n));
    return 0;
}

输出：

F(10) = 55

这个实现的问题

上面的代码虽然正确，但效率很低。计算 F(10) 时，F(8) 会被计算两次，F(7) 会被计算三次，大量重复计算。它的时间复杂度是 O(2ⁿ)，当 n 超过 40 就会明显变慢。

这个问题可以用记忆化或循环解决。这里不是让你背下结论，而是想说明：递归写法优雅，但不代表一定高效。

递归与循环的对比

特性	递归	循环
代码可读性	通常更简洁，思路清晰	有时需要更多变量和判断
性能	有函数调用开销，可能重复计算	通常更高效
栈空间	占用栈空间，太深会溢出	一般固定，更安全
适用问题	树、图、分治、回溯等天然递归结构	简单重复操作、已知次数的迭代

很多能用递归解决的问题也能用循环解决。比如阶乘用循环写：

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

这个版本没有栈溢出风险，效率也更高。但遇到树、图、DFS 这类问题时，递归的代码会更自然。

递归的栈溢出风险

栈空间是有限的。在常见的系统上，一个程序的栈可能只有几 MB。如果递归层数太深，比如 factorial(100000)，栈帧一层一层压上去，最终会超出栈空间，导致栈溢出（stack overflow），程序崩溃。

// 危险示例：递归太深会导致栈溢出
void danger(int n) {
    if (n == 0) return;
    danger(n - 1);
}

int main(void) {
    danger(1000000);  // 层数太大，可能崩溃
    return 0;
}

如何避免栈溢出

确认递归深度在合理范围内。
对于尾递归，某些编译器可以优化成循环，但 C 标准不保证。
如果问题规模很大，考虑用循环或显式栈来模拟递归。

常见错误与注意事项

忘记写终止条件：递归必须能停下来，否则就是死循环加栈溢出。
递归没有向终止条件收敛：比如 factorial(n) 里调用 factorial(n)，永远不会结束。
混淆返回值和输出：递归函数要正确返回结果给上一层，不要在中途直接打印就以为完成了。
忽视重复计算：像斐波那契那样会重复计算的递归，要考虑优化。

递归函数要证明两件事

终止：每次调用都朝基本情况推进，并且最终一定到达；
正确：假设更小问题能正确解决，当前层怎样组合出答案。

以阶乘为例，n 每次减 1，且非负整数最终到 0；若 factorial(n-1) 正确，则乘以 n 得到当前答案。

递归是函数调用自身，适合把大问题拆成结构相同的子问题。
写递归要牢记三要素：终止条件、递归关系、向终止条件收敛。
每次递归调用都会压入函数调用栈，理解栈帧有助于理解递归的执行过程。
递归写法优雅，但要注意栈溢出和重复计算问题。

递归是许多树算法的自然表达。下一篇从普通二叉树开始，先真正实现节点、前中后序遍历和释放，再逐步学习搜索树、堆、哈希表和图。

递归思想与函数调用栈

引入：把大问题拆成小问题

学习目标

什么是递归

递归三要素

1. 终止条件（Base Case）

2. 递归关系（Recurrence Relation）

3. 向终止条件收敛

经典例子一：阶乘

数学定义

代码实现

函数调用栈的执行过程

经典例子二：斐波那契数列

代码实现

这个实现的问题

递归与循环的对比

递归的栈溢出风险

常见错误与注意事项

递归函数要证明两件事

每一层都有独立的自动对象

递归深度和问题规模不总相同

能写出显式栈，就真正理解了递归状态

小结与预告