阶乘递归调用中的逻辑

Question

我正在努力研究递归，也许我太着迷了，但这里是：

在javascript代码中

var factorial = function(number) {
  // If the number is negative, it doesn't have a factorial. Return an
  // impossible value to indicate this.
  if (number < 0) {
    return -1;
  }

  // If the number is zero, its factorial is one.
  if (number === 0) {
    return 1;
  }

  // If the number is neither illegal nor zero, call factorial again,
  // this time passing in a smaller number. Eventually we'll reach 0,
  // causing each call to return to its caller and the recursion terminates.

  return number * factorial(number - 1);
};

factorial(5);

递归函数return如预期的那样是120，但是为什么？

在绘制逻辑时，有两件事让我感到困惑：1) 为什么这甚至是可操作的以及 2) 虽然它是可操作的，但为什么它不能 return -1？

1）为什么这个还能运行？：

将其绘制出来并将 5 作为参数插入，在底部的 return 语句中，我们得到 return 5 * factorial(5 - 1)。为什么这等于预期的 20？我们调用函数不是为了 return 5 * factorial(5-1) 的值吗？我们如何将 5 乘以一个尚未确定的值？如果这只是 5 * (5-1) = 20，那么这是显而易见的，甚至阶乘 (5) * (5-1) = 20 也是有道理的。

2)虽然可以操作，但为什么不可以return -1?:

与上述情况一样，最终，我们将到达递归中的点，它看起来像 1 * factorial(1-1)... 1 * (1-1) = 0。并使用此函数将数字插入自身进行操作，我们的基本情况为 "if the integer plugged in is zero, stop operation and return -1"。为什么这里没有发生这种情况？

抱歉，如果这看起来很简单，我可能会把它变得比需要的更重要。我只是想学习:) .

Answer 1

问得好 - 很高兴您正在深入研究递归！

让我们来看看发生了什么：

我们从 factorial(5) 开始。这 returns 5 * factorial(5-1) 正如您所指出的。为了理解 factorial(5-1) 是什么，我们必须再次调用 factorial 函数。

factorial(5-1)returns4 * factorial(4-1)。让我们将其替换为我们上面的内容。这给了我们 5 * 4 * factorial(4-1)。我们再次执行 factorial(4-1) 并将其替换为。这给了我们 5 * 4 * 3 * factorial(3-1).

如果我们继续，我们会得到 5 * 4 * 3 * 2 * factorial(2-1) 然后 5 * 4 * 3 * 2 * 1 * factorial(1-1)。

现在这里发生了一些不同的事情。 factorial(1-1) returns 1 根据 if 条件：

// If the number is zero, its factorial is one.
if (number === 0) {
    return 1;
}

所以我们有 5 * 4 * 3 * 2 * 1 * 1 = 120 = 5！正如我们所料。除非我们输入负数，否则我们永远不会达到 number == -1 if 条件。对于任何正数，number == 0 条件每次都会捕获。

Answer 2

添加到 winhowes 的回答

How can we multiply 5 by the value of something that hasn't even been determined yet?

嗯，我们不知道，直到我们知道 factorial(5-1) 的值。当 factorial(5-1) 被调用时，我们实际上并没有进行乘法运算，直到我们有一个明确的答案。所以 5 留在那里等待函数调用的结果返回，但随后 4 也等待 factorial(4-1).. 等。一旦最终调用（即 factorial(1)）returns 一个明确的答案，它乘以等待它的任何东西，然后乘以之前的等待呼叫。

所以你有一个 top-down 方法调用，当你有值时，会发生 bottom-up 乘法。如此图所示：

阶乘递归调用中的逻辑

Logic in factorial recursion call

javascript

wordpress

recursion

factorial