你的递归为什么跑得慢？一张“借书单”就能让它飞起来 - 每日分享

你有没有想过这样一个问题：写一个简单的斐波那契递归，当 n=40 时，你的电脑需要计算多少次？答案可能让你震惊——超过 3 亿次！而如果你用了记忆化，只需要 40 次。你没看错，就是 40 次。这中间的差距，不是编译器优化能弥补的，而是你代码设计上的一个“思维陷阱”。今天我们就来揭穿递归的“健忘症”，并给它配上一张高效“借书单”。

递归的“健忘症”：算过的结果全忘了

递归的优雅在于自顶向下地分解问题，但它的致命弱点是重复计算。以斐波那契数列为例：

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

当 n=5 时，fib(3) 被算了 2 次，fib(2) 被算了 3 次，fib(1) 被算了 5 次。画个调用树出来，你会发现大量节点重复出现。这就像你到图书馆借书，第一次查到了《哈利波特》在第 3 排第 2 格，结果下次借同一本书时，你忘了位置，又把整个图书馆翻了一遍。更离谱的是，每本书你都要重复翻好几遍。程序员管这叫“重叠子问题”——问题分解出的子问题反复出现，而你却傻傻地每次都从头算起。

核心矛盾：递归的思维模式是“分而治之”，但它的执行模式却“治而无记”。

解法：一张“借书记录单”——记忆化搜索

解决方案极其简单：既然它健忘，我们就给它配一张记录单。每次算完一个子问题，就把结果记下来，下次再要时直接查单子，不用再算。这就是记忆化（Memoization），也叫“备忘录递归”。

具体做法是用一个数组（或哈希表）存放已经计算过的结果，初始时用一个不可能的值（比如 -1）标记为“未计算”。判断时如果数组值是 -1，说明没算过，正常递归；否则直接返回。

改造后的斐波那契代码：

const int MAX = 100;
int memo[MAX];

void init() {
    for (int i = 0; i < MAX; ++i) memo[i] = -1;
}

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

细节决定成败：为什么不能用 0 初始化？因为 fib(0)=0 是一个有效结果，如果数组初始化为 0，那么 memo[0] 会一直被误认为“没算过”，导致无限循环或错误。而 -1 不是任何斐波那契数，所以是安全的标记。另一个办法是用一个布尔数组单独记录“是否计算过”。

爬楼梯问题：一样的手法

小明爬楼梯，每次走 1 级或 2 级，问走到第 n 级有多少种走法。递推关系与斐波那契完全相同，只是边界不同：第 0 级和第 1 级都是 1 种。用记忆化后，n=40 瞬间出结果，而不需要等几十秒。

思考一个问题：你能直接用循环从底向上算吗？当然可以，但记忆化递归的写法更贴近问题的自然分解，尤其适用于状态转移不太容易用循环描述的复杂问题（比如多维度 DP）。

不是所有递归都能用记忆化——来看一道反例

有个题目叫“阿尔法乘积”：对于一个整数，如果不是个位数，就把它各位非 0 的数字乘起来，重复这个过程直到得到个位数。比如 4018224312 最终得到 8。

递归实现很直接：

int alpha(int x) {
    if (x < 10) return x;
    int prod = 1;
    while (x) {
        if (x % 10 != 0) prod *= x % 10;
        x /= 10;
    }
    return alpha(prod);
}

这个递归有重叠子问题吗？仔细想想，每一步的乘积都是新的数字，几乎不会重复。因为每个数经过一次运算就变成另一个完全不同的数，很难出现同一个中间值被算两次的情况。所以你给它加一个缓存数组，命中率几乎为零，反而白白增加了内存开销和查找时间。

结论：记忆化不是万能的。它只对“含有重叠子问题的递归”有效。判断标准很简单：画递归树，看看是否存在重复节点。如果每个节点只出现一次（比如遍历二叉树），那记忆化无用武之地。

尾递归优化 vs 记忆化：两条不同的路

你可能听说过“尾递归优化”。它要求递归调用是函数的最后一条语句，并且返回值直接返回，不参与其他运算。编译器可以复用当前栈帧，避免栈溢出。但这和记忆化是两码事：尾递归解决的是栈空间问题，而记忆化解决的是时间重复计算问题。

比如求 n 的阶乘，用尾递归可以写成：

int fact(int n, int acc) {
    if (n == 0) return acc;
    return fact(n-1, n * acc);
}

这里没有重叠子问题（每个 n 只出现一次），所以记忆化没用，但尾递归可以优化。而斐波那契有大量重叠，记忆化是更好的选择。

实践中的坑与建议

数组大小要够：算 fib(100) 时，把 MAX 设为 100 没问题，但如果你要算 fib(1000)，-1 标记可能导致数组越界。建议使用 vector 或动态内存分配。
边界条件别漏：比如爬楼梯问题，n=0 要返回 1（一种都不走也算一种），很多人漏掉，导致递归一直减到负数。
记忆化是动态规划的前奏：理解记忆化后，你离动态规划只有一步之遥。动态规划的“自底向上”填表法本质上就是把记忆化的递归改成循环，省去递归开销。建议学完记忆化后，就去刷几道 DP 入门题（比如背包问题、数塔问题），你会发现很多递归加缓存就是标准解法。

关于作者

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

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

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