recursion - 记忆递归阶乘函数如何提高效率？

Question

var lookup = {};
function memoized(n) {
  if(n <= 1) { return 1; }

  if(lookup[n]) {
    return lookup[n];
  }

  lookup[n] = n * memoized(n - 1);
  return lookup[n];
}

对比

function fact(n) {
  if(n <= 1) { return 1; }
  return n * fact(n-1);
}

如果我们称事实（3）

使用第二种方法，我们得到 --> 3 * (2 * (1))

将结果存储在哈希中的效率增益是多少。是否仅适用于对同一函数的后续调用？如果您只调用该函数一次，我看不出您将如何获得任何收益。

使用记忆的斐波那契函数，即使只有一个函数调用，仍然可以提高效率。要获得第 n 个斐波那契数，如果您不记忆，您将在每个 fib(n) 上重复 fib(n-1) 和 fib(n-2) 的计算。我没有在阶乘函数中看到这种情况。

Answer 1

实际上，使用一次并没有提高效率。只有多次使用此方法才能提高效率

Answer 2

因为您将先前计算的阶乘结果存储在lookup.

所以假设如果有另一个n=5已经计算过的阶乘调用，它只会返回lookup[5]，因此计算该数字的阶乘不需要进一步的递归调用。

因此，如果它要服务于许多请求，它会更有效率。

Answer 3

当函数多次调用自身时，记忆化将适用于一次性函数调用。基本上分支成几个递归路径。

以斐波那契为例。因为它会包含类似return fib(n - 1) + fib(n - 2)的东西，所以传递记忆值是很有意义的，这样一个分支可以重用另一个分支的结果。

Factorial 是一种直接自上而下的算法，因此它不会为一次性调用获得任何收益，除非像示例中那样，memoized 版本存储在函数本身之外。

对于像斐波那契这样的“分支”算法，您可以在记忆结构周围使用闭包，使其对外部完全不可见。你只需要为它工作。在斯卡拉：

def fib(n: Int): Int = {
val memo = new mutable.HashMap[Int, Int]()

def fibRec(n: Int, memo: mutable.HashMap[Int, Int]): Int =
  if (n < 2) {
    memo(n) = n
    n
  } else {
    memo(n) = fibRec(n - 1, memo) + fibRec(n - 2, memo)
    memo(n)
  }

fibRec(n, memo)
}

Answer 4

确切地！我也看不到阶乘代码中的记忆化有任何好处，因为我们不会再次调用任何函数。

例如。

fact(5) -> 5 * fact(4) -> 4 * fact(3) -> 3 * fact(2) -> 2* fact(1)

在阶乘程序中永远不会发生冗余调用。所以阶乘代码中不需要记忆。

Answer 5

只是想增强No Idea For Name的答案。如前所述，这里使用的记忆是重用先前执行的结果。

我从以下视频中截取屏幕截图，它很好地解释了如何使用 Memoized Factorial。

Memoized Factorial：JS 代码执行的可视化 - YouTube
https://www.youtube.com/watch?v=js9160AAKTk