斐波那契数列

算法

二分递归：时O(2^n)，空O(1)

int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

线性递归：时O(n)，空O(n)

int fib(int n, int& prev) {
    if (n == 0) {
        prev = 1;  //fib(-1)=1,fib(0)=0
        return 0;
    }
    else {
        int prevprev;
        prev = fib(n - 1, prevprev);
        return prev + prevprev;
    }
}

迭代：时O(n)，空O(1)

int fib(int n) {
    int f = 1, g = 0;
    while (n-- > 0) {
        g = g + f;
        f = g - f;
    }
    return g;
}