带记忆化与无记忆化的递归斐波那契算法空间复杂度差异咨询

嘿，咱们来好好对比这两种斐波那契实现的空间复杂度差异，核心要从递归调用栈和额外存储的记忆数组这两个维度来看：

1. 不带记忆化的递归实现 #

先看你的代码：

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

这种实现的空间复杂度是 O(n)，开销全部来自递归调用栈。

为什么？因为递归调用是深度优先的：计算fib(n)时，会先一路递归到fib(1)或fib(0)，此时调用栈里会依次压入fib(n)、fib(n-1)、fib(n-2)……fib(1)，总共n层。虽然后续会回溯计算fib(n-2)等分支，但栈的最大深度始终是n，不会超过这个值。而且这个实现没有用任何额外存储结构保存中间结果，所以总空间就是递归栈的O(n)。

（顺带提一句，这种实现的时间复杂度是O(2^n)，因为存在大量重复计算，但空间上只吃栈的开销。）

2. 带记忆化的递归实现 #

再看带记忆化的代码：

public static int fib(int n, int[] mem){ 
    if(n ==0 || n ==1 ){ 
        return n; 
    } 
    if(mem[n] > 0 ) { 
        return mem[n]; 
    } 
    mem[n] = fib(n-1,mem) + fib(n-2,mem); 
    return mem[n]; 
}

这种实现的空间复杂度同样是 O(n)，但由两部分组成：

• 递归调用栈的空间：还是O(n)。因为记忆化避免了重复计算，每个fib(k)只会被调用一次，递归路径是fib(n)→fib(n-1)→…→fib(1)，栈的最大深度依然是n。
• 记忆数组mem的空间：数组大小是n+1（要存储从mem[0]到mem[n]的所有结果），这部分也是O(n)的开销。

把两者加起来，总空间复杂度还是O(n)（线性空间的常数项可以忽略），但和不带记忆化的实现相比，它多了一块专门存储中间结果的数组空间，换来了时间复杂度从O(2^n)降到O(n)的巨大提升。

简单总结：

• 不带记忆化：空间复杂度O(n)，仅消耗递归调用栈
• 带记忆化：空间复杂度O(n)，消耗递归调用栈+记忆数组空间

虽然两者的渐近空间复杂度相同，但实际运行时，带记忆化的实现会占用更多的实际内存（因为多了一个数组），不过这是用空间换时间的典型案例。

内容的提问来源于stack exchange，提问作者Satish K