JavaScript 递归函数示例

摘要: 在本教程中，您将学习如何使用递归技术开发 JavaScript 递归函数，该函数是自身调用的函数。

JavaScript 递归函数简介

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

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

function recurse() {
    // ...
    recurse();
    // ...
}
Code language: JavaScript (javascript)

递归函数始终具有停止自身调用的条件。否则，它将无限地调用自身。因此，递归函数通常如下所示

function recurse() {
    if(condition) {
        // stop calling itself
        //...
    } else {
        recurse();
    }
}Code language: JavaScript (javascript)

通常，您使用递归函数将一个大问题分解成更小的问题。通常，您会在数据结构（如二叉树和图）以及二分查找和快速排序等算法中找到递归函数。

让我们来看一些使用递归函数的示例。

1) 一个简单的 JavaScript 递归函数示例

假设您需要开发一个从指定数字倒计时到 1 的函数。例如，从 3 倒计时到 1

3
2
1

以下是 countDown() 函数

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

countDown(3);Code language: JavaScript (javascript)

此 countDown(3) 仅显示数字 3。

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

显示数字 3。
并调用 countDown(2)，它显示数字 2。
并调用 countDown(1)，它显示数字 1。

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

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

countDown(3);Code language: JavaScript (javascript)

此 countDown(3) 将一直运行，直到调用堆栈大小超过，如下所示

Uncaught RangeError: Maximum call stack size exceeded.Code language: JavaScript (javascript)

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

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

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

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        countDown(nextNumber);
    }
}
countDown(3);Code language: JavaScript (javascript)

输出

3
2
1

countDown() 似乎按预期工作。

但是，如函数类型教程中所述，函数的名称是实际函数对象的引用。

如果函数名称在代码中的某个地方被设置为 null，则递归函数将停止工作。

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

let newYearCountDown = countDown;
// somewhere in the code
countDown = null;
// the following function call will cause an error
newYearCountDown(10);Code language: JavaScript (javascript)

错误

Uncaught TypeError: countDown is not a functionCode language: JavaScript (javascript)

脚本工作原理

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

代码导致错误，因为 countDown() 函数的主体引用 countDown 函数名称，该名称在调用函数时被设置为 null。

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

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

    let nextNumber = fromNumber - 1;

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

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);Code language: JavaScript (javascript)

2) 计算 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);
}Code language: JavaScript (javascript)

基本情况

函数以一个“if”语句开始，该语句检查 n 是否小于或等于 1。
如果 n 为 1 或更小，则函数只返回 n。这是基本情况，作为递归的停止条件。

递归情况

如果基本情况不满足（即 n 大于 1），则函数进入 if 语句后的块。
函数返回 n 与自身调用（参数为 (n - 1)）的结果之和。这就是递归发生的地方。

工作原理

例如，如果您调用 sum(3)，则函数首先检查 3 是否小于或等于 1（基本情况不满足）。
由于它不是基本情况，因此它计算 3 + sum(2)。现在，它自身调用参数为 2。
在下一个递归调用 sum(2) 中，它计算 2 + sum(1)。
同样，在下一个递归调用 sum(1) 中，它到达基本情况并返回 1。
现在，前面的调用已解析：2 + 1 得出 3，3 + 3 得出最终结果 6。

终止

递归不断发生，将问题分解成更小的子问题，直到到达基本情况。
到达基本情况后，函数开始展开，将来自每个递归级别的结果组合起来，直到获得最终结果。

总结

递归函数是一个自身调用的函数，直到不再调用为止
递归函数始终具有一个条件，用于停止函数自身调用。

本教程对您有帮助吗？