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

这是一个使用“Helper Method Recursion”的解决方案:

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