拆套娃：递归算法的时间与空间复杂度

递归就像俄罗斯套娃——每一层套娃里都装着一个小一点的套娃，直到最小的那个不再装了。在编程中，递归就是函数调用自己。当我们写了一个递归程序后，最关心的问题是：它跑得快不快？占不占内存？这就是复杂度估算要干的事。简单说，时间复杂度告诉我们程序要花多少步（时间），空间复杂度告诉我们在运行时最多占多少“格子”（内存）。学会估算，就能避免写出“指数爆炸”的慢程序。

什么是递归？为什么我们要关心它的复杂度？

先看一个生活中的例子：你要数一个套娃里有几层。你打开最外面的大套娃，发现里面有个小一点的，再打开，又有一个……直到打开最后一个最小的套娃，里面是空的。你数了数，一共打开了5层。这个“打开套娃”的动作，就是递归函数的行为——每打开一层，就调用一次自己（下一层），直到遇到空套娃（终止条件）。

在编程中，计算一个数的阶乘 n! 就是典型的递归：n! = n × (n-1)!，而 0! = 1。代码像这样：

int factorial(int n) {
    if (n == 0) return 1;          // 最小的套娃，不再拆了
    return n * factorial(n - 1);   // 调用一个更小的“自己”
}

当程序运行时，它会一层一层地“往下拆”，直到拆到最小的那个（n=0），然后一层一层地“往回组装”。
递归算法的复杂度，就像问：“拆套娃需要花多少时间？”和“同时有多少个套娃被打开（占空间）？”

为什么要估算？
如果你写了一个递归程序，结果 n=100 时电脑直接卡死或崩掉，那就是因为复杂度太高。提前估算能帮你决定：是用递归，还是改成循环？要不要加记忆化？

时间消耗：递归要花多少时间？

1. 两个关键因素

递归调用的总次数（类似套娃的个数）
每次递归执行的语句数量（不算递归调用本身）

比如阶乘：每次递归除了调用自己，只做一次乘法 n * ...，所以每次执行常数时间。总调用次数是 n+1 次（从 n 到 0）。所以时间 = 次数 × 每次时间 = (n+1) × 常数 ≈ O(n)。

2. 用“递归树”来理解

以斐波那契数列的递归为例：

int fib(int n) {
    if (n == 0 || n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

当 n=5 时，递归调用就像一棵树：

                fib(5)
               /      \
          fib(4)      fib(3)
         /     \      /    \
     fib(3)  fib(2) fib(2) fib(1)
     /   \    /  \   /  \
 fib(2)fib(1)...

树的每一层：调用次数翻倍（大约）。
树的高度：从根结点到叶子结点的最长路径，这里高度是 n。
结点总数：约 2^n 个。

所以 fib(n) 的时间复杂度是 O(2^n)（指数级）。这意味着 n 每增加1，时间大约翻倍。当 n=40 时，调用次数已经超过 1000 亿次！你想想，如果每次调用要 1 纳秒，也要 100 秒才能跑完。当 n=50，程序就会慢得像蜗牛爬，甚至卡死。

生活中的例子： 老师让你报数，规则是：第 n 个人报的数等于前面两个人报的数之和（类似斐波那契）。如果每个人都要问前面两个人，那整个教室会乱成一锅粥，每个人都在重复问同样的问题——这就是指数级时间复杂度。

3. 常见递归的时间复杂度速查表

递归模式	例子	时间复杂度	直观解释
线性递归（每次只调一次自己）	阶乘、二分查找	O(n)	像一条直线，调用 n 次
分治递归（每次调两三个自己）	归并排序、斐波那契（未优化）	O(2^n) 或 O(n log n)	像一棵树，分支越多越耗时
树形递归（每次调固定常数个）	汉诺塔	O(2^n)	同上，指数爆炸

4. 估算小技巧：看“递归公式”

把递归执行的次数写成数学公式，比如：

阶乘：T(n) = T(n-1) + 1 → 累加得 T(n) = n + 常数 → O(n)
斐波那契：T(n) = T(n-1) + T(n-2) + 1 → 约等于 2^n
二分查找：T(n) = T(n/2) + 1 → 约等于 log₂n 次

（对于中小学生，不需要推导公式，记住：每次只调一次自己的，最多 n 次；每次调两次自己的，可能到 2^n 次 就够用了。）

空间占用：递归要占多少内存？

1. 关键：递归调用栈的深度

递归函数在执行时，每调用一次自己，编译器就会在内存中“压入”一个函数帧（就像套娃里被打开的一层）。只有当前正在执行的那一组嵌套调用才会同时占用空间。

比如阶乘 factorial(5) 的执行过程：

factorial(5)  → 压栈（等待 factorial(4) 的结果）
  factorial(4) → 压栈
    factorial(3) → 压栈
      factorial(2) → 压栈
        factorial(1) → 压栈
          factorial(0) → 返回1
        factorial(1) 返回1
      factorial(2) 返回2
    factorial(3) 返回6
  factorial(4) 返回24
factorial(5) 返回120

同时存在的栈帧数量 = 递归的最大深度 = n+1（从5到0共6层）。
所以空间复杂度 = O(n)。

生活中的例子： 你在玩叠叠乐积木，每放一块积木（每调用一次递归），就要在桌上摞起来。当积木摞到最高的时候（递归深度最大），就是同时占用积木最多的时候。空间复杂度就是问：叠到最高时，一共叠了多少块？

2. 再看斐波那契

虽然斐波那契递归调用了很多次（2^n 次），但是同时最多打开的栈帧深度仍然是 n。因为每次调用深度+1，然后返回，再换另一条分支。所以 fib(n) 的空间复杂度也是 O(n)。

新手容易犯的错误： 以为调用次数多，空间也大。其实空间只看“最多同时有几层”，不看总共调用次数。就像叠积木：你可以拆了又搭、搭了又拆很多次，但最高的时候只有那么几层。

3. 空间复杂度速查

递归例子	递归深度	空间复杂度
阶乘	n	O(n)
斐波那契（未优化）	n	O(n)
二分查找	log n	O(log n)
归并排序	log n	O(log n)（忽略辅助数组）

总结：递归的空间复杂度 = 最大递归深度 × 每个栈帧的大小。每个栈帧通常只存几个局部变量，所以看深度就够了。

如何快速估算复杂度？

1. 三步法

找递归公式：写出 T(n) 与调用次数的关系。
画递归树：看树有多少层，每层有多少结点。
时间看结点总数，空间看层数（深度）。

2. 一个简单的“分数判断法”

如果递归函数只调用一次自身（如阶乘）→ 时间 O(n)，空间 O(n)。
如果递归函数调用两次自身（如普通斐波那契）→ 时间 O(2^n)（指数爆炸），空间 O(n)。
如果递归函数每次把问题减半（如二分查找）→ 时间 O(log n)，空间 O(log n)。

举一反三：优化递归可以降低复杂度

1. 记忆化（备忘录）

把斐波那契算过的结果存起来，避免重复计算：

int memo[1000];                // 备忘录，存已经算过的结果，初始为0
int fib_memo(int n) {
    if (n == 0 || n == 1) return 1;
    if (memo[n] != 0) return memo[n];  // 如果已经算过，直接返回
    memo[n] = fib_memo(n-1) + fib_memo(n-2);
    return memo[n];
}

这样每个 n 只算一次，时间复杂度降为 O(n)，空间复杂度 O(n)（加上数组空间）。

2. 迭代（循环）

直接改成循环，彻底去掉递归：

int fib_iter(int n) {
    int a = 1, b = 1;            // a 代表 fib(0), b 代表 fib(1)
    for (int i = 2; i <= n; ++i) {
        int c = a + b;           // 下一个数
        a = b;                   // 往前移动
        b = c;
    }
    return b;
}

时间 O(n)，空间 O(1)（常数空间）。

所以能不用递归就不用递归，除非递归写起来特别简单（比如树的遍历），并且 n 不大。

新手常犯的错误

忘记写终止条件：导致无限递归，最终栈溢出（程序崩溃）。
例如：把 if (n == 0) return 1; 写成了 if (n > 0) return n * factorial(n-1);，但没处理 n==0 的情况。
误以为空间复杂度也指数级：以为斐波那契调用次数多，空间也是 O(2^n)。实际上空间只跟递归深度有关，是 O(n)。
没考虑递归深度过大导致栈溢出：比如 n=100000 的阶乘，递归深度 100000，很可能超过系统栈大小（通常几兆字节，每个栈帧几十字节，够用但深度太大会爆）。这时候应该改成循环。
混淆了“调用的总次数”和“同时存在的调用次数”：时间看总次数，空间看同时存在的次数。

完整可运行的代码示例

下面是一个完整的 C++ 程序，包含阶乘、斐波那契（未优化和记忆化）以及一个“打印数字”的递归例子。你可以复制到编译器里运行，观察输出。

#include <iostream>
using namespace std;

// 1. 阶乘递归
int factorial(int n) {
    if (n == 0) return 1;              // 终止条件
    return n * factorial(n - 1);       // 每次只调一次自身
}

// 2. 斐波那契（未优化，指数级）
int fib_slow(int n) {
    if (n == 0 || n == 1) return 1;   // 终止条件
    return fib_slow(n - 1) + fib_slow(n - 2);  // 调两次自身
}

// 3. 斐波那契（记忆化优化）
int memo[1000] = {0};                 // 全局备忘录，初始全0
int fib_memo(int n) {
    if (n == 0 || n == 1) return 1;
    if (memo[n] != 0) return memo[n]; // 已计算过，直接返回
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

// 4. 打印数字递归（演示空间复杂度）
void print_num(int n) {
    if (n == 0) return;               // 终止条件
    cout << "进入第" << n << "层" << endl;
    print_num(n - 1);                 // 调一次自身
    cout << "离开第" << n << "层" << endl;
}

int main() {
    // 测试阶乘
    cout << "5! = " << factorial(5) << endl;   // 输出 120

    // 测试斐波那契
    cout << "fib_fast(10) = " << fib_memo(10) << endl;  // 输出 89
    // 小心：fib_slow(40) 已经非常慢，建议只测小 n
    cout << "fib_slow(10) = " << fib_slow(10) << endl;  // 也输出 89

    // 测试打印数字，观察递归栈
    cout << "\n--- 打印递归过程 ---" << endl;
    print_num(3);

    return 0;
}

运行结果将是：

5! = 120
fib_fast(10) = 89
fib_slow(10) = 89

--- 打印递归过程 ---
进入第3层
进入第2层
进入第1层
离开第1层
离开第2层
离开第3层

注意看 print_num 的输出：它先一层层“进入”，到底后再一层层“离开”。这正好对应了递归调用栈的压栈和出栈过程。同时存在的栈帧深度最大是 3（n=3,2,1），所以空间复杂度 O(n)。

递归算法的时间与空间复杂度估算