-2

有人能解释一下这个递归函数是如何产生 5 * 4 * 3 * 2 * 1 来得到 120 的吗？

var factorial = function(n){
   if (n === 0)
       return 1;
   else
       return n * factorial(n - 1); 
};

factorial(5); // spits out 120

如果我们像示例中那样使用 5，那么一旦我们到达 else 语句就不会

return n * factorial(n - 1);

转换为 '返回 5 乘以阶乘函数（5-1）；5次...

4

4 回答 4

4

我觉得这个递归函数感觉像是一个“for循环”，我错了吗？

不，递归和循环有很多共同点。特别是，它们都具有终止条件非常重要。:-) 在这种情况下，终止条件是n === 0.

理解这一点的最好方法是在调试器中单步执行代码。您的浏览器有一个，因此您可以将该代码放在一个页面中并加载它并浏览它。

为了让你开始：

  1. 你打电话factorial(5)。因为nis not === 0，所以用( )factorial调用自身n - 14

  2. 现在我们已经递归了一个级别，我们正在运行factorial(4)（调用factorial(5)仍然没有返回，它正在等待我们）。由于nis not === 0，我们调用factorial(3)并等待它返回。

  3. ...冲洗，重复直到factorial(0)被调用。由于n === 0为真（此时，有 5 个调用factorial未完成且已堆积），factorial(0)返回1，我们可以开始展开堆积的调用。

  4. 现在factorial(1)可以通过将它得到的结果乘以( )factorial(0)的副本并返回它来完成。n1

  5. ...这让我们factorial(2)完成并乘以2...

  6. ...冲洗重复...

或者用另一种方式显示嵌套（递归）：

阶乘(5)
    返回 5 * 阶乘（4）
        返回 4 * 阶乘（3）
            返回 3 * 阶乘（2）
                返回 2 * 阶乘（1）
                    返回 1 * 阶乘（0）
                        返回 1

而且因为你不能得到足够的图表（或者至少我不能）：

阶乘(5) 阶乘(4) 阶乘(3) 阶乘(2) 阶乘(1) 阶乘(0)
    调用 ---------->
                    调用 ---------->
                                    调用 ---------->
                                                    调用 ---------->
                                                                    来电----------->
                                                                                     n 为 0，所以
                                                                                     返回 1
                                                                                             |
                                                                    返回 1 * 1<------------+
                                                                            = 1
                                                                              |
                                                    返回 2 * 1<------------+
                                                            = 2
                                                              |
                                    返回 3 * 2<------------+
                                            = 6
                                              |
                    返回 4 * 6<------------+
                            = 24
                              |
    返回 5 * 24<------------+
            = 120

结果：120

旁注：该函数不允许负数；它可能在一开始就使用警卫......

于 2013-07-16T13:37:34.617 回答
3

n变化：

5 * factorial(5-1) = 5 * 4 * factorial(4-1) = 5 * 4 * 3 * factorial(3-1) = 5 * 4 * 3 * 2 * factorial(1-1) = 5 * 4 * 3 * 2 * 1

n为了使这个函数更好，你可以在等于时停止它1，因为 1 的阶乘是 1：

var factorial = function(n){
   if (n === 1 || n === 0)
       return 1;
   else
       return n * factorial(n - 1); 
};
于 2013-07-16T13:37:38.163 回答
2

这个函数说：如果你想计算阶乘（5），好吧，那真的只是

5 * factorial(4)

如果你想计算阶乘（4），那真的只是 4 * 阶乘（3）

5 * 4 * factorial(3)

factorial(3) 的问题是它实际上只是 3 * factorial(2)

5 * 4 * 3 * factorial(2)

等等。但是当你进入阶乘（0）时，函数最终停止（因为这种if n == 0情况）并返回 1，没有任何进一步的递归。所以你得到

5 * 4 * 3 * 2 * 1

return n * factorial(n - 1)转换为（在第一次运行时）“返回 (5 * 4!)”。它没有做任何事情5次。

于 2013-07-16T13:35:05.980 回答
1

如果我们像示例中那样使用 5，那么一旦我们到达 else 语句就不会

返回 n * 阶乘（n - 1）；

转换为 '返回 5 乘以阶乘函数（5-1）；5次...

不，它将转换为“返回 n 乘以阶乘函数 (n-1)”（5 次，因为 n 从 5 开始，递减并进入 else 子句，直到达到 0）。

  1. 首次输入函数时，n 等于 5。
  2. if 子句检查 n 是否等于 0。它不是，所以它转到：
  3. else 子句。这转化为“返回 5 乘以阶乘函数（您所在的函数）（5 - 1）。
  4. 当您输入阶乘函数时，n 现在是 4。

重复所有这些步骤，直到 n 等于 0。然后 if 子句为真，函数将返回 1。

所以 1 从阶乘（0）返回。Factorial(1) 返回 1 * factorial(0)，所以 1 * 1 = 1。

Factorial(2) 返回 2 * factorial(1)，所以 2 * 1 = 2。

Factorial(3) 返回 3 * factorial(2)，所以 3 * 2 = 6。

Factorial(4) 返回 4 * factorial(3)，所以 4 * 6 = 24。

Factorial(5) 返回 5 * factorial(4)，所以 5 * 24 = 120。

于 2013-07-16T13:38:59.763 回答