斐波那契记忆化实现：左值引用与右值引用传参差异分析

一、两个版本的运行行为与性能差异 #

运行行为差异 #

1. 逻辑正确性与适用场景：两个版本单次调用（不外部传入memo）的计算结果都是正确的，但适用场景存在明显区别：
   • Version 1 支持外部传入左值memo对象，你可以自行持有memo，多次调用fib函数时可以复用之前缓存的结果，比如先算fib(10, memo)再算fib(20, memo)，第二次不需要重复计算1~10的结果。
   • Version 2 的memo参数是右值引用，无法直接绑定左值对象，不能直接传入外部持有的memo复用缓存；每次调用如果使用默认参数，都会生成新的临时map对象，多次调用fib会从头开始计算，没有缓存复用能力。如果你非要给Version 2传入外部创建的memo，只能用std::move(m)的方式，调用完成后原m对象就处于有效但未定义的状态，无法继续使用，还是实现不了缓存复用的需求。
2. 隐性风险：Version 2 中fib(n - 1, std::move(memo)) + fib(n - 2, std::move(memo))的写法存在隐形隐患：如果后续修改函数把参数改为值传递（而非右值引用），会立刻出现逻辑错误——C++不规定加法操作数的求值顺序，先求值的子调用会把memo的所有权移走，后求值的子调用拿到空的memo，计算结果完全错误。

性能差异 #

• 单次计算单个n的场景下，两个版本性能几乎一致，都只需要O(n)时间复杂度，所有递归调用共享同一个memo缓存，没有重复计算。
• 多次计算多个n的场景下，Version 1可以复用缓存，性能远高于每次都要重新生成缓存的Version 2。

二、更推荐的实现 #

优先选择Version 1，优势如下：

• 灵活性更高，既支持单次调用时内部自动创建memo，也支持外部持有memo实现缓存复用。
• 写法更符合常规C++编程习惯，没有隐形的求值顺序风险，可读性和可维护性更好。

三、给Version 1添加默认参数的方案 #

左值引用无法绑定临时右值，所以不能直接写map& memo = map{}，最常用的解决方案是函数重载：

using map = std::unordered_map<int, unsigned long long>;

// 对外的无memo参数接口，适合单次调用场景
unsigned long long fib(int n) {
    map memo;
    return fib(n, memo);
}

// 原有带memo参数的版本保留，适合需要复用缓存的场景
unsigned long long fib(int n, map& memo) {
    if(memo.find(n) != memo.cend()) return memo[n];
    if(n <= 2) return 1;
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

这个方案没有任何额外运行开销，接口清晰，是工业界的标准实现方式。

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