以下 fib 函数计算第 n 项斐波那契数（fib(0)=0, fib(1)=1），其时间复杂度为 $O(n)$。

1 int fib(int n) {2   if (n <= 1) return n;3   return fib(n-1) + fib(n-2);4 }