Javascript 斐波那契递归

Question

请参阅下面的代码-

function fib(x) {
    if (x === 0) {
        return 0;
    } else if (x === 1) {
        return 1;
    } else {
        return fib(x-1) + fib(x-2);
    }
}

我有 2 个问题，关于递归的基本问题。

1)当递归调用fib()时，它不是会像n取值0、-1、-2一样无限地进行下去……既然上面的代码有效，那么停止条件是什么呢？

2) 如果我们从上面的代码中删除 if() 或 else if() 条件，则会出现最大堆栈大小错误。 if 或 else if 不是停止条件之一吗？或者两者结合起来作为停止条件？

Answer 1

它停止是因为 x 最终变成 1 或 0，在这种情况下 fib 不会调用自身不再如此，因为 if (x === 0) 或 if (x === 1) 开始起作用。

or are both of them combined a stopping condition?

正是如此。您需要两者，因为 fib 既使用 x-1 调用自身，又使用 x-2 调用自身(如果 x 不是 0 或 1)。如果删除 else if (x === 1)，请想一下当 x 为 1 并且它用以下命令调用自身时会发生什么x-2。 :-)

如果您添加一些工具，这可以更容易地可视化:

function fib(x, indent) {
  var rv;
  
  log(indent + "fib(" + x + ")");
  if (x === 0) {
    log(indent + "Stopping (x is 0)");
    rv = 0;
  } else if (x === 1) {
    log(indent + "Stopping (x is 1)");
    rv = 1;
  } else {
    log(indent + "Recursing");
    rv = fib(x-1, indent + " ")+fib(x-2, indent + " ");
  }
  log(indent + "fib(" + x + ") returning " + rv);
  return rv;
}
fib(4, " ");

function log(msg) {
  var p = document.createElement('pre');
  p.innerHTML = String(msg);
  document.body.appendChild(p);
}

pre {
  font-family: monospace;
  margin: 0;
  padding: 0;
}