面试题：C++ 中如何通过优化递归函数避免堆栈溢出

Question

在 C++ 中，编写一个简单的递归函数来计算斐波那契数列。要求通过至少一种方法优化该递归函数，以避免堆栈溢出，并解释优化的原理。

Answer 1

#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;
}

优化原理

1. 避免重复计算：通过使用 std::unordered_map 作为记忆化存储，每次计算一个斐波那契数之前，先检查哈希表中是否已经存在该数的计算结果。如果存在，直接返回结果，避免了重复递归计算，大大减少了计算量。
2. 防止堆栈溢出：递归函数调用会在调用栈上分配空间，随着递归深度增加，调用栈空间可能耗尽导致堆栈溢出。优化后的方法减少了递归调用的次数，降低了调用栈的深度，从而有效避免了堆栈溢出问题。