如何使用 Memoization 优化递归函数？-JavaScript中文网-JavaScript教程资源分享门户

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

推荐答案

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

实现 Memoization 通常有两种方式：

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

-- -------------------- ---- -------
-------- ------------- -
  ----- ----- - ---
  ------ -------- --------- -
    ----- --- - ---------------------
    -- ------------ -
      ------ -----------
    -
    ----- ------ - ---------------- ------
    ---------- - -------
    ------ -------
  --
-

-- --------------------------
-------- ------------ -
  -- -- -- -- ------ --
  ------ ----------- - -- - ----------- - ---
-

----- ----------------- - -------------------

---------------------- ------------
--------------
------------------------- ------------

---------------------- ------------
----------------------
------------------------- ------------

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

-- -------------------- ---- -------
-------- ------------- -
  ----- ----- - --- ------
  ------ -------- --------- -
    ----- --- - ---------------------
    -- ---------------- -
      ------ ---------------
    -
    ----- ------ - ---------------- ------
    -------------- --------
    ------ -------
  --
-


-- ----------------------
-------- ------------ -
  -- -- --- -- ------ --
  ------ - - ---------------
-


----- ----------------- - -------------------

---------------------- ------------
--------------
------------------------- ------------


---------------------- ------------
----------------------
------------------------- ------------

本题详细解读

什么是 Memoization?

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

为什么递归函数需要 Memoization？

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

如何实现 Memoization？

创建缓存:
- 可以使用 JavaScript 对象 ( {} ) 或者 ES6 的 Map 对象来存储缓存的结果。对象适合参数可以转换为字符串作为 key 的情况， Map 则更灵活，允许使用对象和数组作为键。
- 缓存的 key 需要唯一标识函数的输入参数，可以使用 JSON.stringify(args) 来将参数转换为字符串。
返回闭包:
- 使用闭包来保持缓存对象的私有性和持久性。闭包函数会接收原函数作为参数，并返回一个新函数。
- 新函数在被调用时，首先检查缓存中是否存在该参数对应的结果。如果存在，则直接返回缓存的结果。
- 如果不存在，则调用原函数计算结果，并将结果存入缓存中，然后返回。
使用 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 没有太大意义。

纠错
反馈