JavaScript

JavaScript 计算阶乘 - 迭代和递归

Posted by cl9000 on August 18, 2021

不畏惧失败是创造力的一个基本要素。——<艾尔文·兰德博士>

介绍

一个数的阶乘是该整数与所有小于或等于它的正整数的乘积。它必须是一个正整数 - 否则，逻辑会扩展到负无穷大。换句话说 - 计算阶乘意味着将数字和 1 之间的所有整数相乘。

0！按照惯例等于 1，并且不遵循标准规则
阶乘由我们计算阶乘的整数表示，后跟感叹号。
3！表示阶乘的3
为了计算阶乘，我们将数字乘以每个小于它的整数，直到达到 1：

1
2
4! = 4 * 3 * 2 * 1
4! = 24

本教程中，将学习如何使用 JavaScript 使用循环和递归计算整数的阶乘。

使用循环计算

我们可以同时使用 while 循环和 for 循环来计算阶乘。通常只需要一个用于循环终止的计数器和我们正在计算阶乘的提供的数字。

使用 for 循环计算阶乘

1
2
3
4
5
6
7
8
9
10
11
12
function getFactorialForLoop(n) {
    let result = 1;
    if (n > 1) {
        for (let i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
    else {
        return "n 必须是正数";
    }
}

从数学上讲，这些是等效的陈述：

1
1 * 2 * 3 * 4 ... * n = n * (n-1) * (n-2) * (n-3) * (n-4) ... * (n - (n- 1))

为简化起见，(n - (n-1))将始终等于1。
演示

1
2
3
4
5
var inp = window.prompt("Enter a number: ");
inp = parseInt(inp);

alert("The result is: " + getFactorialForLoop(inp));
// 4！是4 * 3 * 2 * 1，结果为24。

使用 while 循环计算阶乘

1
2
3
4
5
6
7
8
function getFactorialWhileLoop(n){
    let result = 1;
    while (n > 1) {
        result = result * n;
        n -= 1;
    }
    return result;
}

与 for 循环非常相似。除了这一次我们从移动 n 向 1 -更接近于数学上的定义。让我们测试一下我们的功能：

1
2
3
var inp = window.prompt("Enter a number: ");
inp = parseInt(inp);
alert("The result is: " + getFactorialWhileLoop(inp));

使用递归计算

递归函数是调用自身的函数。乍一听可能有点吓人，但请耐心等待，您会发现递归函数很容易理解。

一般来说，每个递归函数都有两个主要组成部分：基本情况和递归步骤。

基本案例是问题的最小实例 - 这就是重复的内容。也是一个中断，一个将返回一个值并退出递归的情况。就阶乘函数而言，基本情况是我们返回阶乘的最后一个元素，即1。

如果没有基本情况或不正确的基本情况，您的递归函数可能会无限运行，从而导致溢出。

递归步骤——顾名思义——是函数的递归部分，在这里整个问题被转化为更小的问题。如果递归步骤未能缩小问题，那么递归可以无限运行。

考虑阶乘的重复部分：

  • **5！**是 5 * 4 * 3 * 2 * 1。
    // 也知道：
  • 4 * 3 * 2 * 1 是 4！.

换句话说，5！是 5 * 4!，和 4！是 4 * 3! 等等。

所以我们可以这么说 n! = n * (n-1)!。这将是我们阶乘的递归步骤！

阶乘递归在达到 1 时结束。这将是我们的基本情况。1 如果 n 是 1 或更少，我们将返回，覆盖零输入。

递归阶乘函数：

1
2
3
4
5
6
7
8
function getFactorialRecursively(n){
    if (n <= 1){
        return 1;
    }
    else{
        return n * getFactorialRecursively(n-1);
    }
}

如您所见，if块体现了我们的基本情况，而 else块则涵盖了递归步骤。

1
2
3
4
var inp = window.prompt("Enter a number: ");
inp = parseInt(inp);

alert("The result is: " + getFactorialRecursively(inp));

我们得到相同的结果。但这一次，引擎盖下的内容相当有趣：

你看，当我们输入输入时，函数会检查if块，由于 3 大于 1，它会跳到 else 块。在这个块中，我们看到了一行return n * getFactorialRecursively(n-1);。

我们暂时知道n的当前值，它是3，但getFactorialRecursively(n-1)仍有待计算。

然后程序再次调用同一个函数，但这次我们的函数以 2 作为参数。它检查 if 块并跳到 else 块并再次遇到最后一行。现在，n的当前值2
但程序仍然计算 getFactorialRecursively(n-1).

因此它再次调用该函数，但这次是 if 块，或者更确切地说，基类成功返回 1 并从递归中跳出。

遵循相同的模式向上，它返回每个函数结果，将当前结果与前一个结果相乘，n 并为前一个函数调用返回它。换句话说，我们的程序首先到达阶乘的底部（即 1），然后向上构建，同时在每一步进行乘法运算。

也将函数从调用栈中一一移除，直到 n * (n-1) 返回最终结果。

这通常是递归函数的工作方式。一些更复杂的问题可能需要包含多个基本情况或多个递归步骤的更深层次的递归。但就目前而言，这个简单的递归足以解决我们的阶乘问题！

总结

在本文中，我们介绍了如何使用 for 和 while 循环计算阶乘。我们还学习了 递归 是什么，以及如何使用递归计算阶乘。

参考

关注【公众号】，了解更多。


赏 支付宝打赏 微信打赏

赞赏一下 坚持原创技术分享，您的支持将鼓励我继续创作！



FEATURED TAGS
JavaScript
FRIENDS