Lesson 0010 · 递归

C++ 进阶 — 第 3 课

1. 递归是什么

一句话：函数调用自己，每次把问题缩小一点，直到最简单的情况直接返回。

// 循环版：求 1+2+...+n
int sum(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

// 递归版
int sum(int n) {
    if (n == 1) return 1;              // 终止条件（最简单的情况）
    return n + sum(n - 1);             // 缩小问题：n + 前面 n-1 个的和
}

怎么执行的？以 n=3 为例

sum(3) = 3 + sum(2)
              = 2 + sum(1)
                    = 1          ← 触底，开始返回
              = 2 + 1 = 3
       = 3 + 3 = 6

一路拆下去，触底后再一路算回来 —— 像走楼梯下楼再上楼。

2. 递归两要素

3. 经典例子

阶乘

int fact(int n) {
    if (n == 0) return 1;          // 0! = 1
    return n * fact(n - 1);        // n! = n * (n-1)!
}

斐波那契

int fib(int n) {
    if (n <= 2) return 1;           // fib(1)=1, fib(2)=1
    return fib(n - 1) + fib(n - 2); // fib(n) = fib(n-1) + fib(n-2)
}

最大公约数（辗转相除法）

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

4. 递归 vs 循环

5. 递归的代价 —— 调用栈

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}
// sum(100000) → 10 万个函数调用堆在栈上 → 栈溢出崩溃

每个函数调用占用一小块内存（栈帧），递归太深会爆。一般递归深度别超过几千到几万。

6. 坑点清单

• 没写终止条件：函数会一直调用自己，直到栈被撑爆，程序直接崩溃。
• 规模没缩小：写 sum(n) 里又调 sum(n)，效果和没写终止条件一样。
• 终止条件写错起点：阶乘的边界是 fact(0) = 1，写成 if (n == 1) 会让 fact(0) 一路递归到负数。
• 递归版斐波那契是指数级：fib(40) 会算到天荒地老，因为同一个子问题被反复重算。
• 递归太深会爆栈：sum(100000) 就是 10 万个栈帧，深度一般别超过几千到几万。

7. 小测

8. 动手练习

本课小结

• 递归 = 函数调用自己，把问题缩小直到终止条件。
• 两要素：终止条件 + 缩小规模，缺一不可。
• 循环 vs 递归：循环快、递归优雅。树和图用递归最自然。
• 调用栈：递归太深会溢出，日常几百层没问题。