为什么你的递归程序跑起来像蜗牛？——拆开“套娃”看看复杂度 - 每日分享

你有没有过这样的经历：写完一个递归函数，心里美滋滋，觉得这代码简直优雅到飞起。结果一运行，n=30 的时候还能勉强出结果，n=40 就开始卡顿，n=50 直接让你怀疑电脑是不是中了病毒？

这不是你的电脑老了，也不是编译器抽风了。这是递归算法的时间复杂度在向你发出警告。今天，我们就来拆一拆递归这个“套娃”，看看时间去哪了，空间又去哪了。

递归的本质：函数调用了它自己

递归就像俄罗斯套娃——每一层都装着一个小一点的自己，直到最小的那个不再装了。在编程里，递归就是函数调用自己。比如计算阶乘：

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

这段代码优雅吗？优雅。但它到底跑多快？占多少内存？如果你答不上来，那这个优雅就可能变成灾难。

时间复杂度：拆套娃到底要花多少步？

估算递归的时间复杂度，只需要看两件事：

递归调用的总次数（总共拆了多少个套娃）
每次递归执行的语句数量（每个套娃里装了多少东西）

对于阶乘，每次递归除了调用自己，只做一次乘法，所以每次是常数时间。总调用次数是 n+1 次。所以时间 = (n+1) × 常数 ≈ O(n)。线性复杂度，很友好。

但如果你写的是斐波那契数列的朴素递归呢？

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 个人报的数等于前面两个人报的数之和。如果每个人都要去问前面两个人，整个教室会乱成一锅粥，每个人都在重复问同样的问题——这就是指数级时间复杂度的真实写照。

空间复杂度：同时打开了几个套娃？

时间看总调用次数，但空间只看同时存在的调用次数——也就是递归的最大深度。

还拿阶乘举例。当 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。所以空间复杂度 = O(n)。

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

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

快速估算：三步法

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

再给你一个更简单的“分数判断法”：

只调用一次自身（如阶乘）→ 时间 O(n)，空间 O(n)
调用两次自身（如朴素斐波那契）→ 时间 O(2^n)，空间 O(n)
每次把问题减半（如二分查找）→ 时间 O(log n)，空间 O(log n)

优化：别让“套娃”无限膨胀

既然朴素递归这么坑，有没有救？当然有。

方法一：记忆化（备忘录）

把已经算过的结果存起来，避免重复计算：

int memo[1000];                // 备忘录，存已经算过的结果
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)（加上数组空间）。

方法二：迭代（循环）

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

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 不大。

新手最容易踩的坑

忘记写终止条件 → 无限递归，栈溢出，程序崩溃。
误以为空间复杂度也指数级 → 斐波那契空间是 O(n) 不是 O(2^n)。
没考虑递归深度过大 → n=100000 的阶乘，递归深度 100000，很可能超过系统栈大小。这时候应该改成循环。
混淆“调用的总次数”和“同时存在的调用次数” → 时间看总次数，空间看同时存在的次数。

最后说两句

递归就像拆套娃——拆的时间（时间复杂度）看总共拆了多少个套娃，占的空间（空间复杂度）看同时打开了几个套娃。学会估算，你就不再害怕递归爆炸。

进阶的方向：动态规划（记忆化递归的升级版）、尾递归优化（有些编译器能自动优化成循环）、栈与函数调用的底层原理。理解了这些，你的算法功底会更上一层楼。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）