JavaScript 中的 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 高阶函数：

硅基智能

基于Web3.0的元宇宙，去中心化的互联网，高质量、沉浸式元宇宙直播平台，用数字化重新定义直播

62

查看详情

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 能极大提升递归函数性能，尤其是在动态规划类问题中效果显著。关键是理解何时该缓存、如何设计缓存结构。

以上就是JavaScript 中的 Memoization 技术如何优化递归函数的性能？的详细内容，更多请关注php中文网其它相关文章！