如何记忆递归因子函数使其更有效率？

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

将结果存储在哈希中的效率增益是多少.它仅用于后续调用相同的函数吗？如果你只调用一次这个函数,我看不出你会得到什么.

使用memoized Fibonacci函数,即使只有一个函数调用,仍然可以提高效率.为了获得第n个斐波纳契数,如果你没有记忆,你将重复计算每个fib(n)上的fib(n-1)和fib(n-2).我没有看到在阶乘函数中发生这种情况.

Answer 1

实际上,使用它一次就没有效率.只有在多次使用此方法时才能获得效率

Answer 2

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

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

因此,如果要提供许多请求,它会更有效率.