记忆递归阶乘函数如何使其更有效？

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];
}

vs。

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是一种直接的自上而下的算法，因此除非像示例中那样，已记忆的版本存储在函数本身之外，否则一次调用将不会获得任何好处。

对于像fibonacci这样的“分支”算法，您可以在已记忆的结构周围使用闭包，以使外部完全看不到它。您只需要为此功能即可。在Scala中：

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)
}