记忆递归阶乘函数如何使其更有效? [英] How does memoizing a recursive factorial function make it more efficient?

问题描述

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)

If we call fact(3)

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

With the second method we get --> 3 * (2 * (1))

将结果存储在散列中的效率提高是多少?它仅用于后续对同一函数的调用吗?如果只调用一次函数，我看不到会有什么收获.

What is the efficiency gain of storing the result in a hash. Is it only for subsequent calls to the same function? I can't see how you would gain anything if you are only calling the function once.

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

With the memoized Fibonacci function, even if there is only one function call there is still an efficiency gain. To get the nth fibonacci number, if you do not memoize, you will be repeating the calculation for fib(n-1) and fib(n-2) on each fib(n). I don't see this happening in the factorial function.

推荐答案

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

actually there is no efficiency gained by using it once. you gain efficiency only if this method is used several times

这篇关于记忆递归阶乘函数如何使其更有效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！