算法分析例子：糟糕的递归调用

考虑以下计算斐波那契数的递归程序

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

记\(T(N)\)为调用函数\(fib(N)\)所花费的时间，由于\(T(0)\)和\(T(1)\)只花费常数时间，可令\(T(0)=T(1)=1\)。这样一来，对于\(N \geq 2\)，有\(T(N) = T(N-1) + T(N-2) + 2\)，其中2指的是基准情形判断（if (n <= 1)）以及加法（fib(n - 1) + fib(n - 2)）的时间开销。

因为\(T(N) = T(N-1) + T(N-2) + 2\)，而\(fib(N) = fib(N-1) + fib(N-2)\)，所以\(T(N)\)严格大于\(fib(N)\)。而fib(N)是指数增长的(Wikipedia上的证明)，因此\(T(N)\)也是指数增长的，故上述递归程序的时间复杂度是指数级的。

graph LR
	fib5-->fib4
	fib5-->fib3
	fib4-->fib3
	fib4-->fib2
	fib3-->fib2
	fib3-->fib1
	fib2-->fib1
	fib2-->fib0

把递归调用展开，就可以看到程序运行缓慢的原因：做了太多的重复计算，\(fib(N) = fib(N-1) + fib(N-2)\)中的\(fib(N-1)\)和\(fib(N-2)\)在计算完之后就被抛弃了，随后它们的值又要被重新计算出来。

作为反面例子，这个程序很好地体现了递归算法设计乃至程序设计的一大准则——“计算任何事情不要超过一次”。