斐波那契数列c++递归优化

斐波那契数列是一种经典的数列，每个数字是前两个数字之和。在C++中，递归实现斐波那契数列直观易懂，但是效率较低，因为会有大量的重复计算。为了优化递归版本，可以使用动态规划的思想，通过引入一个数组`f`来存储已经计算过的斐波那契值，避免重复。

以下是使用C++优化后的斐波那契数列递归实现：

#include <vector>
size_t fibonacci(size_t n) {
    std::vector<int> f(n + 1, 0);
    if (n <= 1)
        return n;
    else {
        f[0] = 0; // 第0项
        f[1] = 1; // 第1项
        for (size_t i = 2; i <= n; ++i)
            f[i] = f[i - 1] + f[i - 2]; // 记录并返回已计算的值
        return f[n];
    }
}

在这个优化版中，我们首先初始化一个大小为`n+1`的数组，并设置基本情况（n小于等于1）。然后从第三个位置开始遍历，每次计算都利用之前保存的结果，减少了重复计算。