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

int fib(int n) {
    if (n <= 1) return n;
    int f0 = 0, f1 = 1, cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = f0 + f1;
        f0 = f1;
        f1 = cur;
    }
    return cur;
}