JS 如何用记忆化优化递归计算？

Question

JS 如何用记忆化优化递归计算？

仓乃文 · Accepted Answer

记忆化（Memoization）是将函数上次计算结果缓存起来，下次相同输入直接返回缓存，避免重复计算。对递归函数如斐波那契数列优化效果显著。

基础实现：
```javascript
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.apply(this, args);
    cache.set(key, result);
    return result;
  };
}
```

优化斐波那契数列：
```javascript
const fib = memoize(function (n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

fib(40);  // 有缓存秒出结果，无缓存需要数秒
```

补充说明：
- 斐波那契无缓存时间复杂度 O(2^n)，有缓存降为 O(n)
- Map 的 key 用 JSON.stringify，注意对象参数顺序不同会导致缓存未命中
- 缓存会占用内存，不适合输入空间无限大的函数
- React 的 useMemo 就是记忆化的应用，避免组件重复计算