Memoization通过缓存已计算结果避免重复求解子问题，将斐波那契递归时间复杂度从O(φⁿ)降至O(n)，核心是“查缓存→计算→存结果”三步判断。
递归中的重复计算，本质是同一个子问题被反复求解多次。Memoization 就是给函数“记笔记”——算过一次，就把结果存起来；下次遇到相同输入，直接翻笔记，不再重算。
为什么重复计算会发生？
以斐波那契为例：fib(5) = fib(4) + fib(3)，而 fib(4) = fib(3) + fib(2)，fib(3) 就被调用了两次；再往下，fib(2)、fib(1) 会被调用更多次。整个调用树里大量分支重叠，导致时间复杂度飙升到 O(φⁿ)（接近 O(1.618ⁿ)）。
Memoization 的核心操作
它不是改算法逻辑，而是加一层“查缓存 → 算新值 → 存结果”的判断：
- 每次进入函数，先检查输入参数是否已在缓存中
- 若命中，立刻返回缓存值
- 若未命中，执行原逻辑计算，把结果写入缓存再返回
几种常见实现方式
手动传参缓存（推荐初学）：把缓存对象作为参数传入，清晰可控
function fib(n, cache = {}) {
if (n in cache) return cache[n];
if (n <= 1) return n;
cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
return cache[n;
}闭包封装缓存（复用性强）：用高阶函数包装，缓存私有化
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn(...args);
cache.set(key, result);
return result;
};
}
const memoFib = memoize(fibWithoutCache);语言内置方案（省心）：Python 用 @lru_cache，JavaScript 可引入 memoizee 支持对象/异步等复杂场景
要注意的关键点
Memoization 有效，但不是万能的：
- 只适用于纯函数（相同输入必得相同输出）
- 缓存键要能准确反映输入差异，比如对象参数需深比较或序列化
- 缓存长期不清理可能吃内存，大范围输入建议设最大容量或 TTL
- 对单次调用、无重复参数的场景，加缓存反而拖慢速度
不复杂但容易忽略——关键是识别出“哪些子问题会反复出现”，然后让函数记得自己算过什么。
