下面用递推方式计算斐波那契数列第 n 项的程序，时间复杂度是 $O(2^n)$。

1int fib(int n) {2   if (n <= 1) return n;3   int f0 = 0, f1 = 1, cur = 0;4   for (int i = 2; i <= n; i++) {5      cur = f0 + f1;6      f0 = f1;7      f1 = cur;8   }9   return cur;10}