递归

本节学会什么

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

为什么需要它

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

最小可运行示例

#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 开始输出”。

关键过程与易错点

• 每个递归函数都要先写清边界条件，否则调用不会停止。
• 每次递归调用都必须让问题更接近边界，例如 n - 1，而不是仍然传 n。
• 先用 n = 1、2、3 手工展开调用，再写代码；不要一开始就用大数据。
• 递归有调用层数限制。深度很大时，循环或显式栈可能更合适。

动手检查

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

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

立即练习