斐波那契递归会重复计算是因为存在重叠子问题，如fibonacci(5)中fibonacci(3)被多次调用，导致时间复杂度升至o(2ⁿ)；可通过数组或哈希表记忆化优化，避免重复求解。
为什么斐波那契递归会重复计算？
调用 fibonacci(5) 时，fibonacci(3) 会被 fibonacci(4) 和 fibonacci(3) 各自调用一次；再往下，fibonacci(2) 出现频次更高。整棵树里大量子问题被反复求解，时间复杂度从 O(n) 暴涨到 O(2ⁿ)。
这不是代码写错了，而是暴力递归天然的结构缺陷——**重叠子问题**。只要子问题输入相同、输出确定，就该只算一次。
用数组缓存结果：最直接的记忆化
在函数外声明全局或静态 vector<int></int>，初始化为 -1 表示“未计算”。每次进入函数先查表，命中就直接返回；否则递归计算并存入表中。
-
memo数组大小要覆盖所有可能输入（比如memo[100]支持n ） - 必须用
if (memo[n] != -1) return memo[n];判断，不能只靠if (memo[n])（0 是合法结果） - 记得在递归调用后赋值：
memo[n] = fibonacci(n-1) + fibonacci(n-2);
示例关键片段：
vector<int> memo(100, -1);
int fibonacci(int n) {
if (n == 0 || n == 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibonacci(n-1) + fibonacci(n-2);
return memo[n];
}</int>
哈希表替代数组：应对稀疏或大范围输入
当 n 可能很大（如 1e9）或取值非常稀疏（只调用几个特定值），用 unordered_map<int int></int> 更省空间。
- 查找开销略高（平均 O(1)，但有哈希碰撞），但避免了数组越界和内存浪费
- 插入前无需预分配，动态增长，适合运行时才知道输入范围的场景
- 注意键类型要支持哈希，
int、long long都可以，自定义结构需手动提供哈希函数
用法与数组类似，只是把 memo[n] 换成 memo.count(n) ? memo[n] : ... 或用 memo.try_emplace()。
尾递归优化不解决重复计算问题
尾递归（如带累积参数的阶乘）能让编译器复用栈帧、防止栈溢出，但它**不减少计算次数**。它只是让单条递归路径更轻量，对多叉树状分支（如斐波那契）完全无效。
真正降复杂度的只有记忆化或改写为迭代 DP。别混淆“避免栈溢出”和“避免重复计算”——这是两个独立问题，需要不同手段。
实际写递归时，先画小规模递归树，一眼看出哪些节点重复，再决定是否加 memo。没验证过重叠，就别急着加缓存。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
