递归斐波那契函数的指数时间复杂度疑问

先看你给出的递归斐波那契实现：

var fib = function(n) {
    if (n===0) return 0
    if (n===2 || n===1) return 1
    return fib(n-1) + fib(n-2)
};

你对调用次数的估算有误，这个递归实现的函数调用次数是指数级增长的，并非线性。

调用次数的递推推导 #

我们用C(n)表示计算fib(n)时的总调用次数：

• 当n=0时，仅调用fib(0)一次，所以C(0)=1
• 当n=1或n=2时，各自仅调用一次，C(1)=1，C(2)=1
• 当n>2时，计算fib(n)会先触发fib(n-1)和fib(n-2)的调用，再加上自身这一次调用，因此递推公式为：
  C(n) = C(n-1) + C(n-2) + 1

解这个递推式可以得到：C(n) = 2*fib(n+1) - 1，而斐波那契数本身是指数增长的（fib(n) ≈ φⁿ/√5，其中φ≈1.618是黄金分割比），所以总调用次数C(n)自然也是指数级的。

实际例子验证 #

举几个具体数值就能看出增长趋势：

• n=3：调用次数C(3)=3次（fib(3)、fib(2)、fib(1)）
• n=4：调用次数C(4)=5次（fib(4)、fib(3)、fib(2)、fib(1)、fib(2)）
• n=5：调用次数C(5)=9次
• n=6：调用次数C(6)=15次
• n=10：调用次数C(10)=177次

可以看到，n每增加1，调用次数的增长倍数接近黄金分割比φ（≈1.618），这完全符合指数时间复杂度的定义——运行时间随输入规模增长呈指数级增长，指数时间复杂度并不要求每增加1输入就严格翻倍，只要存在大于1的常数k，使得运行时间是O(kⁿ)即可，这里k=φ，显然满足条件。

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