面试题：C++ Lambda 表达式递归实现斐波那契数列并优化

Question

编写一个 C++ 程序，利用 Lambda 表达式递归实现斐波那契数列的计算。同时，考虑到斐波那契数列递归计算的低效性，使用适当的优化策略（如记忆化）来提升性能，说明优化思路和实现方法。

Answer 1

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> memo;
    auto fibonacci = [&fibonacci, &memo](int n) -> int {
        if (n <= 1) {
            return n;
        }
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo[n] = result;
        return result;
    };

    int n = 10; // 这里以计算第10个斐波那契数为例
    std::cout << "第 " << n << " 个斐波那契数是: " << fibonacci(n) << std::endl;

    return 0;
}

优化思路

1. 记忆化原理：斐波那契数列计算过程中，存在大量重复计算。例如计算 fib(n) 时会多次计算 fib(n - 1) 和 fib(n - 2) 等子问题。记忆化就是使用一个数据结构（这里使用 std::unordered_map）来存储已经计算过的结果，下次需要计算相同子问题时，直接从存储结构中获取，避免重复计算，从而提升性能。
2. 实现方法：
   • 定义一个 std::unordered_map 类型的变量 memo 用于存储已经计算过的斐波那契数。
   • 在 Lambda 表达式内部，每次计算前先检查 memo 中是否已经存在要计算的数 n 的结果，如果存在则直接返回；否则计算结果并存储到 memo 中。