为何纯递归实现斐波那契比带Memoization的递归更快？

开发者阿泽

2026-7-21

为什么错误实现的Memoization递归斐波那契反而比纯递归慢？

核心问题：你的Memoization实现根本没生效
你写的带Memo的代码里，int[] dp = new int[n+1];是函数内的局部变量，每次递归调用fib时都会新建一个完全独立的数组。这意味着：
- 每次递归调用的dp数组都是全新的，元素初始值都是0，if (dp[n] != 0)这个判断永远不会触发，等于完全没用到缓存
- 反而每次调用都要额外承担数组创建、初始化的开销，还有多余的判断语句执行成本，这些都是纯递归没有的额外消耗
正确的Memoization实现应该共享缓存
要让缓存生效，必须让所有递归调用共享同一个缓存容器（比如类成员变量、静态变量）。比如修改后的正确实现：
```
class Solution {
    private int[] dp;
    public int fib(int n) {
        if (n < 2) return n;
        dp = new int[n + 1];
        dp[1] = 1;
        return helper(n);
    }
    
    private int helper(int n) {
        if (dp[n] != 0) {
            return dp[n];
        }
        dp[n] = helper(n-1) + helper(n-2);
        return dp[n];
    }
}
```
这里的dp数组是类成员，所有递归调用的helper方法都共享这个数组，真正实现了重复计算的缓存，时间复杂度才是O(n)，运行速度会远快于纯递归。
LeetCode运行结果的本质
你当前的带Memo代码，实际执行逻辑和纯递归几乎一样，但多了数组创建、初始化和多余判断的开销，所以耗时更长。只有正确实现缓存的Memoization版本，才能体现出时间复杂度的优势，击败更多用户。