JavaScript 递归

递归是一种编程技术，其中函数通过反复调用自身来解决问题。例如，

// Program to countdown till 1

// recursive function
function counter(count) {

    // display count
    console.log(count);

    // condition for stopping
    if(count > 1) {

        // decrease count
        count = count - 1;

        // call counter with new value of count
        counter(count);
    } else {

        // terminate execution
        return;
    };
};

// access function
counter(5);

输出

5
4
3
2
1

在上面的示例中，我们有一个名为 counter() 的函数，它接受参数 count，这是我们倒计时到 **1** 的起始点。

counter() 函数首先显示 count，然后检查 count 的值是否大于 **1**，即 count > 1。

如果 count > 1 的计算结果为 true，程序将减少 count 的值，并用 count 的新值调用 counter()（递归）。

否则，如果 count > 1 的计算结果为 false，程序将执行 return 语句，停止递归。

这里，

• counter() 函数是一个 **递归函数**，即一个递归调用自身的函数。
• count > 1 条件被称为 **基本情况**，即指定递归何时必须停止的条件。

注意：没有基本情况，递归函数将不知道何时停止，从而导致 **无限递归**（错误）。

示例：计算数字的阶乘

现在，让我们看一个如何使用递归来计算数字阶乘的示例。

// recursive function
function factorial(num) {

    // base case
    // recurse only if num is greater than 0
    if (num > 1) {
        return num * factorial(num - 1);
    }
    else {
        return 1;
    };
};

let x = 3;

// store result of factorial() in variable
let y = factorial(x);

console.log(`The factorial of ${x} is ${y}`);

输出

The factorial of 3 is 6

在这里，只要 num 变量大于 **1**，factorial() 函数就会递归调用自身。

我们可以将整个递归过程分为两个部分。

第一部分中的迭代包括

1. factorial(3) 返回 3 * factorial(2) 并等待 factorial(2) 计算。
2. factorial(2) 返回 2 * factorial(1) 并等待 factorial(1) 计算。
3. factorial(1) 不满足基本情况，因此直接返回 **1**。

在此之后，第二部分以相反的顺序进行

1. factorial(1) 返回 **1**。
2. factorial(2) 返回 2 * factorial(1)。由于 factorial(1) 返回 1，factorial(2) 返回 2 * 1 = 2。
3. factorial(3) 返回 3 * factorial(2)。由于 factorial(2) 返回 2，factorial(3) 返回 3 * 2 = 6。

最后，从 factorial(3) 返回的值存储在 result 变量中。

// recursive function
function greet() {

    // display "Hello"
    console.log("Hello");

    // call itself
    greet();
};

// access function
greet();

Hello
Hello
Hello
...
RangeError: Maximum call stack size exceeded