JavaScript 递归函数

在 JavaScript 中，如果一个函数在其函数体内部调用该函数的本身，这样的函数就叫做 “递归函数”。递归函数的原理就是：使用一个函数通过不断地调用函数自身，从而循环地处理数据。直到处理到最后一步，再将每一步的计算结果向上一步逐级返回。

注意: 在使用递归函数的过程中一定要有结束递归的判断条件，否则递归会无限制地执行下去，造成死循环，直到程序报错。

JavaScript 递归函数实现 “n 的阶乘”

我们先来看一个最简单的例子，那就是使用 JavaScript 递归函数来实现 n 的阶乘。

示例 1：

运行代码

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title></title>
</head>
<body>
    <script>
        // 定义函数
        function multi(n) {
            if (n <= 1) {
                return 1;
            } else {
                return n * multi(n - 1);
            }
        }

        // 调用函数
        const result = multi(3);
        console.log(result);
    </script>
</body>
</html>

运行结果如下。

分析：

上面示例定义了一个名为 “multi” 的函数，由于该函数内部使用了函数本身，所以它是一个递归函数。multi 函数满足下面的递归关系。这种递归关系，表示的是 1~n 的乘积可以由 n 乘以 1~n-1 的乘积计算得到。如果 n 等于 1，则可以直接得到结果。

n的阶乘公式

使用递归函数 multi() 来计算 3 阶乘，也就是执行 multi(3)，需要以下几步：

第 1 步：multi(3) 等价于 3 * multi(3 - 1)，也就是执行 3 * multi(2)，此时等待 multi(2) 返回结果。
第 2 步：multi(2) 等价于 2 * multi(2 - 1)，也就是执行 2 * multi(1)，此时等待 multi(1) 返回结果
第 3 步：对于 multi(1) 来说，此时 n 等于 1，返回结果为 1，然后就会将结果返回第 2 步。第 2 步拿到了 multi(1) 的返回值，就可以计算得到 multi(2) 的结果，也就是 2 * 1=2。最后把 multi(2) 的结果返回给第 1 步，就可以计算得到 multi(3) 的结果，也就是 3 * 2 = 6。

需要特别注意的是，递归一定要有一个退出条件，否则就会一直递归下去。对于上面这个例子来说，它的递归退出条件就是 n <= 1。

JavaScript 递归函数实现 “斐波那契数列”

知道 JavaScript 递归函数怎么使用之后，再来看一个经典的递归实例：斐波那契数列。斐波那契数列，又称 “黄金分割数列” 或 “兔子数列”，它指的是这样一个数列：0、1、1、2、3、5、8、13、21、34……。对于斐波那契数列，它从第 3 项开始，每一项都等于前两项之和，所以满足下面的公式。

斐波那契数列公式

接下来尝试使用递归函数的方式来求出斐波那契数列前 20 项数字（从 0 项开始），并且将结果打印出来。

示例 2：

运行代码

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title></title>
</head>
<body>
    <script>
        // 定义递归函数
        function fibonacci(n) {
            if (n < 2) {
                return n;
            } else {
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        }

        // 打印结果
        for (let i = 0; i <= 20; i++) {
            console.log(fibonacci(i));
        }
    </script>
</body>
</html>

运行结果如下。

分析：

在上面例子中，我们定义了一个名为 “fibonacci” 的函数，该函数是一个递归函数。对于 fibonacci() 函数来说，它递归的退出条件为 n < 2。

实际上，递归函数并没有想象中那么复杂，你只需要把递归的条件找出来，然后在函数体内根据一定的规则不断调用函数本身就可以了。

注意，使用递归计算斐波那契数列虽然代码比较简单，但当 n 很大时（比如超过 40），计算速度会变得非常慢。在实际开发中，对于大量计算，我们一般会采用 “循环” 或其他优化算法，而不是直接用这种递归。

思考：如何使用递归函数来实现 1 + 2 + 3 + ... + 100 的和呢？请编写程序来实现一下。