JavaScript 递归函数

JavaScript 递归函数

在本教程中，您将学习如何使用 JavaScript 递归函数，这是一个函数调用自身的函数。

JavaScript 递归函数介绍

递归函数是一个函数，它会调用自身直到它不调用。这种技术称为递归。

假设您有一个函数名为 recurse() 。如果它在其函数体内调用自身，则它是一个递归函数，如下所示：

function recurse() {
    // ...
    recurse();
    // ...
}

递归函数总是有一个停止调用自身的条件。否则，它将无限地调用自己。所以递归函数通常如下所示：

function recurse() {
    if(condition) {
        // 停止调用自身
        //...
    } else {
        recurse();
    }
}

通常，您使用递归函数将大问题分解为较小的问题。您也会在二叉树和图形等数据结构以及二分搜索和快速排序等算法中找到递归函数。

JavaScript 递归函数示例

让我们举一些使用递归函数的例子。

简单的 JavaScript 递归函数

假设你需要开发一个从指定数倒数到 1 的函数，比如从 3 倒数到 1：

3
2
1

以下是 countDown() 函数大概样子：

function countDown(fromNumber) {
    console.log(fromNumber);
}

countDown(3);

这个 countDown(3) 只会浏览器控制台打印数字 3。

要从数字 3 倒数到 1，您可以：

1. 打印数字 3。
2. 然后调用 countDown(2) 打印数字 2 。
3. 最后调用 countDown(1) 打印数字 1 。

以下更改countDown()为递归函数：

function countDown(fromNumber) {
    console.log(fromNumber);
    countDown(fromNumber-1);
}

countDown(3);

这将一直运行 countDown(3) 函数，直到超过调用堆栈大小 Uncaught RangeError: Maximum call stack size exceeded. 如下所示：

Uncaught RangeError: Maximum call stack size exceeded.

…因为它没有条件停止调用函数自身。

当下一个数字为零时，countDown 将停止。因此，您添加一个 if 条件，如下所示：

function countDown(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        countDown(nextNumber);
    }
}
countDown(3);

3
2
1

似乎 countDown() 按预期工作。

然而，正如函数类型教程中提到的，函数的名称是对实际函数对象的引用。如果在代码中的某处将函数名设置为 null ，递归函数将停止工作。

例如，以下代码将导致错误：

let newYearCountDown = countDown;
// 某些逻辑代码
countDown = null;
// 下面的函数调用将会抛出错误
newYearCountDown(10);

错误：未捕获的类型错误，countDown 不是一个函数。

Uncaught TypeError: countDown is not a function

代码是如何工作的：

• 首先，将 countDown 函数名称分配给变量 newYearCountDown。
• 其次，将 countDown 函数引用设置为 null。
• 最后、调用 newYearCountDown 函数。

代码会抛出一个错误，是因为在 countDown() 函数体内将会 countDown 函数名的引用设置 null，然后又再次通过 countDown() 函数的引用调用 countDown。

要修复它，您可以使用命名函数表达式，如下所示：

let countDown = function f(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        f(nextNumber);
    }
}

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);

计算 n 个自然数之和

假设您需要使用递归计算从 1 到 n 的自然数之和。您需要 按如下方式定义 sum() 递归函数：

sum(n) = n + sum(n-1)
sum(n-1) = n - 1 + sum(n-2)
...
sum(1) = 1

sum() 递归函数：

function sum(n) {
  if (n <= 1) {
    return n;
  }
  return n + sum(n - 1);
}

• 递归函数是一个函数，它会调用自己直到它不调用自己才会终止。
• 递归函数总是有一个条件来阻止函数调用自身。