如何使用 Memoization 优化递归函数？

推荐答案

使用 Memoization 可以显著优化递归函数，特别是那些存在大量重复计算的函数。Memoization 的核心思想是缓存中间结果，当函数使用相同的参数再次调用时，直接返回缓存的结果，避免重复计算。

实现 Memoization 通常有两种方式：

1. 使用闭包和对象: 创建一个闭包，在闭包内部用一个对象来存储计算结果。

// www.javascriptcn.com code example
function memoize(func) {
  const cache = {};
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache[key]) {
      return cache[key];
    }
    const result = func.apply(this, args);
    cache[key] = result;
    return result;
  };
}

// 示例：使用Memoization优化递归斐波那契数列
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

const memoizedFibonacci = memoize(fibonacci);

console.time('Original fibonacci');
fibonacci(40);
console.timeEnd('Original fibonacci');

console.time('Memoized fibonacci');
memoizedFibonacci(40);
console.timeEnd('Memoized fibonacci');

1. 使用 Map 对象: Map 对象相比普通对象，在处理非字符串类型的键值时更灵活，尤其适合参数包含对象或数组的情况。

// www.javascriptcn.com code example
function memoize(func) {
  const cache = new Map();
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = func.apply(this, args);
    cache.set(key, result);
    return result;
  };
}


// 示例：使用Memoization优化递归阶乘
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n-1);
}


const memoizedFactorial = memoize(factorial);

console.time('Original factorial');
factorial(20);
console.timeEnd('Original factorial');


console.time('Memoized factorial');
memoizedFactorial(20);
console.timeEnd('Memoized factorial');

本题详细解读

什么是 Memoization?

Memoization 是一种优化技术，它通过存储函数调用的结果（基于传入的参数）来避免重复计算。当函数使用相同的参数再次调用时，直接返回缓存的结果，而不是重新执行函数体。这对于计算密集型函数，特别是递归函数，可以显著提高性能。

为什么递归函数需要 Memoization？

许多递归函数会重复计算相同的子问题，例如斐波那契数列的递归实现中，fibonacci(5) 会重复计算 fibonacci(3) 和 fibonacci(2)。随着输入的增大，重复计算的次数会呈指数级增长，导致性能问题。 Memoization 通过存储已经计算过的结果来避免这些重复计算，从而显著提升性能。

如何实现 Memoization？

1. 创建缓存:

   • 可以使用 JavaScript 对象 ( {} ) 或者 ES6 的 Map 对象来存储缓存的结果。 对象适合参数可以转换为字符串作为 key 的情况， Map 则更灵活，允许使用对象和数组作为键。
   • 缓存的 key 需要唯一标识函数的输入参数，可以使用 JSON.stringify(args) 来将参数转换为字符串。

2. 返回闭包:

   • 使用闭包来保持缓存对象的私有性和持久性。闭包函数会接收原函数作为参数，并返回一个新函数。
   • 新函数在被调用时，首先检查缓存中是否存在该参数对应的结果。如果存在，则直接返回缓存的结果。
   • 如果不存在，则调用原函数计算结果，并将结果存入缓存中，然后返回。

3. 使用 apply:

   • 在调用原始函数时，使用 func.apply(this, args) 可以保证原始函数的 this 指向正确的上下文，同时也能传递所有的参数。

使用示例分析

上述代码示例演示了如何使用 memoize 函数来优化斐波那契数列和阶乘的递归函数。

• 首先定义一个 memoize 高阶函数，它接收一个函数 func 作为参数，返回一个记忆化（memoized）版本的新函数。
• 新函数内部，首先生成一个基于 args 的 key，如果 cache 中已经存在该 key，则直接返回缓存值。
• 如果不存在，则调用 func 计算结果，并将结果存入 cache，然后返回。
• 通过对比使用 memoize 优化后的函数与原始函数执行耗时，可以明显看出优化后的函数性能更高。

注意事项

• Key 的生成: 使用 JSON.stringify 将参数序列化成字符串作为 key 时要注意，如果参数包含循环引用的对象，可能会报错。此时可以使用更复杂的 key 生成方式，如手动递归遍历对象生成 key。
• 缓存大小： 对于参数非常多的情况，缓存可能会占用大量的内存。可以考虑设置缓存的最大容量，使用 LRU 或其他缓存淘汰策略。
• 适用场景： Memoization 适用于那些计算耗时，并且使用相同参数多次调用的函数。对于每次调用参数都不同的函数，使用 memoization 没有太大意义。