Memoization是一种缓存函数输入与输出的技术，用于避免重复计算，特别适用于存在大量重复子问题的递归函数，如斐波那契数列，通过存储已计算结果将时间复杂度从指数级降为接近线性。
Memoization 技术通过缓存函数的执行结果来避免重复计算，特别适合优化递归函数。当递归函数存在大量重复子问题时，比如斐波那契数列或阶乘计算，直接递归会导致指数级的时间复杂度。使用 memoization 后，每个输入参数对应的返回值只需计算一次，后续调用直接从缓存中读取，将时间复杂度降低到接近线性。
什么是 Memoization？
Memoization 是一种将函数的输入和输出结果进行缓存的技术。当下次以相同参数调用函数时，不再执行函数体，而是直接返回缓存的结果。这在纯函数（相同输入始终产生相同输出）场景下非常有效。
递归函数为何需要优化？
以经典的斐波那契数列为例：
不使用 memoization 的递归实现：function fibonacci(n) {
if (n
return fibonacci(n - 1) + fibonacci(n - 2);
}
这个函数会重复计算很多相同的子问题。例如，计算 fibonacci(5) 时，fibonacci(3) 会被调用两次，fibonacci(2) 更是多次。随着 n 增大，性能急剧下降。
立即学习“Java免费学习笔记（深入）”；
如何用 Memoization 优化递归？
我们可以手动添加一个缓存对象，存储已计算的结果：
function fibonacci(n, cache = {}) {
if (n in cache) return cache[n];
if (n
cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
return cache[n];
}
或者封装一个通用的 memoize 高阶函数：
function memoize(fn) {
const cache = {};
return function(...args) {
const key = args.join(',');
if (key in cache) return cache[key];
cache[key] = fn.apply(this, args);
return cache[key];
};
}
然后这样使用：
const memoFib = memoize(fibonacci);
memoFib(50); // 几乎瞬间完成
适用场景与注意事项
Memoization 最适合以下情况：
- 函数是纯函数，无副作用
- 输入参数种类有限，便于构建缓存 key
- 存在大量重复调用相同参数的情况
需要注意的是，缓存会占用内存，如果输入范围过大或参数类型复杂，可能导致内存泄漏。必要时可结合 WeakMap 或限制缓存大小。
基本上就这些。合理使用 memoization 能极大提升递归函数性能，尤其是在动态规划类问题中效果显著。关键是理解何时该缓存、如何设计缓存结构。
