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

你的传统递归实现存在大量重复计算（比如计算fib(5)时会重复计算fib(3)两次、fib(2)三次），时间复杂度为O(2ⁿ)，且递归调用栈会随n增大而持续加深，导致内存消耗高、计算速度慢。以下是几种针对性的优化方案：

1. 记忆化递归（Memoization） #

核心思路是缓存已计算的结果，避免重复计算。可以用数组或哈希表存储中间值，将时间复杂度降至O(n)。

#include <iostream>
#include <unordered_map>

// 缓存已计算的斐波那契值
std::unordered_map<int, long long> memo;

long long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    // 检查缓存，存在则直接返回
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    // 计算并存入缓存
    long long result = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = result;
    return result;
}

int main() {
    int n = 30;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

注意：使用long long类型避免整数溢出（斐波那契数增长极快，int很快会超出范围）。

2. 迭代法（最优空间效率） #

完全消除递归，用循环迭代计算，仅保存前两个值，空间复杂度为O(1)，时间复杂度O(n)，是最实用的优化方案。

#include <iostream>

long long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    long long prev_prev = 0; // 对应fib(0)
    long long prev = 1;      // 对应fib(1)
    long long current;
    for (int i = 2; i <= n; ++i) {
        current = prev + prev_prev;
        prev_prev = prev;
        prev = current;
    }
    return prev;
}

int main() {
    int n = 50;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

3. 尾递归优化 #

修改递归结构，让递归调用成为函数的最后一个操作，此时编译器可将其优化为循环（避免栈溢出），空间复杂度降至O(1)（开启编译器优化时）。

#include <iostream>

// 尾递归：将中间结果作为参数传递，最后一步直接返回递归调用结果
long long fibonacci_tail(int n, long long a = 0, long long b = 1) {
    if (n == 0) {
        return a;
    }
    if (n == 1) {
        return b;
    }
    return fibonacci_tail(n - 1, b, a + b);
}

int main() {
    int n = 40;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci_tail(n) << std::endl;
    return 0;
}

注意：C++标准不强制编译器支持尾递归优化，但GCC、Clang等主流编译器在开启-O2等优化选项时会自动处理。

4. 快速幂方法（O(logn)时间复杂度） #

利用矩阵快速幂或通项公式，将时间复杂度降至O(logn)，适合计算极大的n（如n>1000）。

矩阵快速幂实现： #

#include <iostream>
#include <vector>

using Matrix = std::vector<std::vector<long long>>;

// 矩阵乘法
Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix res(2, std::vector<long long>(2, 0));
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return res;
}

// 矩阵快速幂
Matrix matrix_power(Matrix mat, int power) {
    // 初始化单位矩阵
    Matrix res = {{1, 0}, {0, 1}};
    while (power > 0) {
        if (power % 2 == 1) {
            res = multiply(res, mat);
        }
        mat = multiply(mat, mat);
        power /= 2;
    }
    return res;
}

long long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    Matrix mat = {{1, 1}, {1, 0}};
    Matrix powered = matrix_power(mat, n - 1);
    return powered[0][0];
}

int main() {
    int n = 100;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

说明：斐波那契数可通过矩阵幂表示：[[fib(n+1), fib(n)], [fib(n), fib(n-1)]] = [[1,1],[1,0]]ⁿ，快速幂通过分治法将幂运算时间降至O(logn)。

内容的提问来源于stack exchange，提问作者Anush.