C++中斐波那契数递归与记忆化动态规划函数性能异常问题排查求助

嘿，很高兴你自己定位到了问题根源！让我再详细拆解一下为什么参数里的&会对性能造成这么大的影响：

错误写法的性能陷阱 #

你最初的错误版本用了值传递：

long fib(int n, unordered_map<int, long> mp)

每次递归调用这个函数时，都会把整个unordered_map完整复制一份。随着递归深度增加，哈希表的大小不断变大，每次拷贝的开销会急剧上升——这个拷贝的耗时甚至会远远超过递归重复计算子问题的开销，直接导致记忆化版本反而比纯递归更慢。

正确写法的优势 #

改成引用传递后：

long fib(int n, unordered_map<int, long> &mp)

所有递归调用都会共享同一个unordered_map对象，不会产生任何拷贝开销。此时记忆化的优势才能真正发挥：每个斐波那契数只会被计算一次，后续直接从哈希表中读取结果，时间复杂度从递归的O(2ⁿ)降到了O(n)，性能会有质的提升。

额外优化小建议 #

如果想进一步优化，还可以试试这些思路：

• 把哈希表换成vector<long>，因为斐波那契的n是连续的整数，数组的随机访问比哈希表更快
• 将记忆化容器设为函数内的静态变量，避免每次调用都需要手动传入参数

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