Java递归实现斐波那契数列效率低下的原因咨询

咱们先来看你给出的递归实现代码：

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

这个实现效率低下的核心原因是指数级的重复计算，咱们一步步拆解：

• 递归的逻辑是计算fib(n)时，需要先算fib(n-1)和fib(n-2)，但这两个子问题之间会大量重叠。比如计算fib(5)：

  • fib(5)需要fib(4) + fib(3)
  • fib(4)需要fib(3) + fib(2)
  • fib(3)需要fib(2) + fib(1)
  • fib(2)需要fib(1) + fib(0)
    这里fib(3)被计算了2次，fib(2)被计算了3次，fib(1)被计算了5次——每往上增加一个n，重复计算的量会爆炸式增长。

• 从时间复杂度来看，这个递归实现的时间复杂度是O(2ⁿ)，属于指数级复杂度。指数级增长的特点就是前期看起来还行，但到了某个阈值（比如n=48），总计算量会瞬间突破天文数字，导致CPU长时间忙于重复计算，自然耗时就超过20秒了。

举个直观的例子：n=40时，递归调用次数大概是1亿次左右；n=48时，调用次数会超过400亿次——这么多重复的计算，能不慢吗？

如果要优化的话，你可以用迭代法（时间复杂度O(n)），或者给递归加上记忆化缓存（比如用HashMap存储已经计算过的fib值，避免重复计算），这两种方式都能把效率提升几个数量级。

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