javascript 斐波那契记忆

Question

为了计算斐波那契数列的第 n 项，我使用熟悉的递归函数：

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    return fibonacci(index-2) + fibonacci(index-1);
}

这按预期工作。现在，我尝试将计算出的索引存储在对象中：

var results = {
  0: 0,
  1: 1,
  2: 2
};

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    if(!results[index]){
        results[index] = fibonacci(index-2) + fibonacci(index-1);
    }
}

我知道这实际上并没有提高性能，因为我没有访问结果对象，但我想在记忆之前首先检查我的结果对象是否已正确填充。不幸的是，事实并非如此。对于斐波那契(9)，我得到：

Object {0: 0, 1: 1, 2: 2, 3: 3, 4: NaN, 5: NaN, 6: NaN, 7: NaN, 8: NaN, 9: NaN}

为什么超过 3 的索引会得到 NaN？

Answer 1

这是使用“辅助方法递归”的解决方案：

function fib(n) {
  const memorize = {};

  function helper(n) {
    if (n in memorize) return memorize[n];
    if (n < 3) return 1;
    return memorize[n] = helper(n - 1) + helper(n - 2);
  }

  return helper(n);
}

Answer 2

这是我的解决方案：

function fib(n, res = [0, 1, 1]) {
    if (res[n]) {
        return res[n];
    }

    res[n] = fib(n - 1, res) + fib(n - 2, res);
    return res[n];
}

console.log(fib(155));