递推斐波那契数列

斐波那契（Fibonacci）数列的应用非常多。

【递推公式】

f(n) = n （n=0 或 n=1）
f(n) = f(n-1) + f(n-2) （n≥2）
【参考程序】

// 递归，时间复杂度 O(2^n)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}


// 递推
int fibonacci(int n) {
    if (n <= 1) return n;

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


// 空间换时间，生成斐波那契数列前 n 项（动态规划）
vector<int> generateFibonacci(int n) {
    vector<int> fib(n, 0);
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i < n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib;
}

经典算法

递推斐波那契数列