“如何优化 C++ 中计算斐波那契数的递归算法？”

Question

我正在开发一个项目，涉及使用递归算法在 C++ 中计算斐波那契数。我当前的实现遵循传统的递归方法，但它表现出较大斐波那契数的性能问题。这是我到目前为止所做的：

#include <iostream>

int fibonacci(int n) {    
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 10; // Example: Calculate Fibonacci(10)
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

我注意到，对于超过某个值的斐波那契数，算法会变得很慢并且消耗大量内存。我一直在探索优化该算法的方法，但我不知道从哪里开始。我可以使用任何技术或策略来使其更快、更节省内存吗？如果有任何可以帮助我提高斐波那契计算器性能的指导或代码示例，我将不胜感激。

Answer 1

此代码（几乎）没有运行时成本。 所有数字（最多 30 个）将在编译时计算。

#include <array>
#include <iostream>

template<std::size_t N>
static auto constexpr initialize_fibonacci_numbers()
{
    static_assert(N >= 2);
    std::array<std::uint64_t, N> values{0,1};
    for (std::size_t n = 2; n < N; ++n)
    {
        values[n] = values[n - 1] + values[n - 2];
    }
    return values;
}

int main()
{
    static constexpr auto fibonacci_number = initialize_fibonacci_numbers<30>();

    std::cout << fibonacci_number[12];

    return 0;
}