递归

本节学会什么

• 判断一个问题能否拆成更小的同类问题
• 找出递归边界和递归步骤
• 用小数据跟踪递归调用过程

为什么需要它

有些问题的解决步骤和原问题相同，只是规模更小，例如枚举所有选择、遍历树或不断拆分区间。递归让函数调用自身来描述这种结构，但必须保证规模变小并最终停在边界。

最小可运行示例

#include <iostream>

void print_down(int n) {
    if (n == 0) {
        return;
    }
    std::cout << n << ' ';
    print_down(n - 1);
}

int main() {
    print_down(5);
    std::cout << '\n';
    return 0;
}

输出 5 4 3 2 1。n == 0 是边界；其他情况先输出当前数，再把问题缩小为“从 n - 1 开始输出”。

再看一个把结果返回给上一层的例子：求 1 到 n 的和。

#include <iostream>

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

int main() {
    std::cout << sum(3) << '\n';
    return 0;
}

输出 6。调用 sum(3) 时先一路向下调用到边界 sum(0)，再从最深处逐层向上计算。这里「更小的同类问题」的结果真正被使用了：sum(3) 的答案依赖 sum(2) 的答案，这就是目标一说的“把问题拆成更小的同类问题”。

flowchart TD
    s3["① sum(3): 求 3 + sum(2)"] --> s2["② sum(2): 求 2 + sum(1)"]
    s2 --> s1["③ sum(1): 求 1 + sum(0)"]
    s1 --> s0["④ sum(0): 到达边界，返回 0"]
    s0 --> r1["⑤ sum(1) 得到 0，返回 1"]
    r1 --> r2["⑥ sum(2) 得到 1，返回 3"]
    r2 --> r3["⑦ sum(3) 得到 3，返回 6"]

    classDef forward fill:#dcefe9,stroke:#087c6c,color:#202827
    classDef boundary fill:#fff4db,stroke:#b76e00,color:#202827
    classDef backtrack fill:#fbe3dd,stroke:#b9472f,color:#202827
    class s3,s2,s1 forward
    class s0 boundary
    class r1,r2,r3 backtrack

关键过程与易错点

• 每个递归函数都要先写清边界条件，否则调用不会停止。
• 每次递归调用都必须让问题更接近边界，例如 n - 1，而不是仍然传 n。
• 递归调用前的语句先执行，调用后的语句要等整层返回后再执行；把 print_down 的输出语句移到递归调用之后，输出就会变成升序。
• 先用 n = 1、2、3 手工展开调用，再写代码；不要一开始就用大数据。
• 递归有调用层数限制。深度很大时，循环或显式栈可能更合适。

动手检查

写 print_up(int n)，使它输出 1 到 n。提示：递归调用放在输出语句之前。对 n = 3 展开每一层，检查输出顺序。

把 print_down 的边界改错成 n < 0 后运行小数据，观察多输出了什么，再修正。

手算 sum(4) 的调用展开和每一层返回的值，再运行程序核对。

立即练习