JavaScript使用递归实现斐波那契数列

Question

我正在尝试使用递归来实现斐波那契数列，但遇到了 maximum callstack exceeded 错误。

代码:

var genFib = function(count, limit, fibArray) {
  if (count === undefined || count === null) {
    var count = 0;
  }

  if (fibArray === undefined || fibArray === null) {
    var fibArray = [0, 1];
  }

  if (count === limit) {
    console.log(fibArray);
    return fibArray;
  }

  var pushFibNo = function(fibArray) {
    fibArray.push(fibArray[fibArray.length - 1] + fibArray[fibArray.length - 2]);
    return fibArray;
  };

  // console.log(count++);
  // console.log(limit);
  // console.log(pushFibNo(fibArray));

  return genFib(count++, limit, pushFibNo(fibArray));

};

genFib(null, 50, null);

页面底部的三个console.logs输出了正确的数字，但仍然出现了maximum callstack错误。

- user6017908

---

找到了 - 在底部的返回语句中，你不能将 count++ 作为参数传入，而必须传入 count += 1。有人能解释一下为什么吗？ - user6017908

请看我的回答，你总是使用相同的计数。 - pishpish

两个答案都是正确的。 - Kevin B

我认为count++在你将其发送到递归调用之后会增加1，因此实际上你总是发送初始值，即在本例中为零。请参见@janje的答案。 - ThisClark

@BrandonKent -- “尾递归优化”，count++ 表示代码在递归返回后还有更多的执行，而 count +=1 则会在递归之前执行 -- 因此优化器可以在递归中删除调用栈。 - Soren

Answer 1

++在后缀和前缀表示法中的行为不同。

来自MDN：

如果使用后缀运算符（例如x++），则返回递增前的值。如果使用前缀运算符（例如++x），则返回递增后的值。

这意味着您总是在递增之前传递count，导致堆栈溢出问题。

要解决问题，请更改：

return genFib(count++, limit, pushFibNo(fibArray));

致

return genFib(++count, limit, pushFibNo(fibArray));

- pishpish

Answer 2

if (count === undefined || count === null) {
    var count = 0;
}

您已经重新声明了“count”。这将覆盖计数参数，而if(count === limit)则永远不会被调用。

- Massimo Franciosa

---

这是错误的，第一次运行后 count 始终为 0。它不会被重新声明。 - pishpish

即使变量在if语句内部，JavaScript也会将其视为已声明。不过，上面的代码还存在其他问题（请参见另一个解决方案）。 - Massimo Franciosa

好的想法，然而重新声明一个变量并不会使其失去其值。 - pishpish

你是对的。在那里声明一个变量仍然不正确，但问题的根源在别处（使用++运算符）。 - Massimo Franciosa

同意，使用 var 是不必要的且容易引起混淆的。 - pishpish

Answer 3

问题在于您在这一行中使用了后置递增。

return genFib(count++, limit, pushFibNo(fibArray));

然后你总是使用相同的值调用函数，如果你使用前置运算符应该可以工作。

return genFib(++count, limit, pushFibNo(fibArray));

- cralfaro