使用JavaScript了解递归

某些问题更适合用递归解决。例如，斐波那契数列这样的序列具有递归定义。序列中的每个数字都是序列中前两个数字的和。需要构建或遍历树状数据结构的问题也可以用递归来解决。训练自己进行递归思考将赋予你强大的技能来解决此类问题。

在本教程中，我将逐步讲解几个递归函数的工作原理，并向你展示一些系统地定义递归函数的技术。

内容：

• 什么是递归？
• 数字递归
• 列表递归
• 构建列表
• 尾递归
• 总结

什么是递归？

递归定义的函数是用其简化版本自身定义的函数。这是一个简化的示例：

function doA(n) {
    // ...
    if (n > 0) {
        doA(n-1);
    }
}

为了从概念上理解递归的工作原理，我们将看一个与代码无关的示例。假设你负责接听公司里的电话。由于这是一家繁忙的公司，你的电话有多条电话线，因此你可以同时处理多个电话。每条电话线在听筒上都有一个按钮，当有来电时，按钮会闪烁。今天，当你上班并打开电话时，有四条线路同时闪烁。所以你开始接听所有电话。

你拿起第一条线并告诉他们：“请稍候。”然后你拿起第二条线并将他们也放在待机状态。接下来，你拿起第三条线并将他们放在待机状态，依此类推。最后，当你完成每个电话后，你回到之前的来电者，完成该电话并挂断。

此示例中的每个电话都类似于函数中的递归调用。当你接到电话时，它会被放入调用堆栈（用代码来说）。如果你不能立即完成一个电话，你就把它放在待机状态。如果你的函数调用无法立即计算，它将保留在调用堆栈中。当你能够接听电话时，它就会被接起。当你的代码能够计算函数调用时，它就会从堆栈中弹出。请记住这个比喻，当你查看以下代码示例时。

数字递归

所有递归函数都需要一个基本情况，以便它们能够终止。但是，仅仅向我们的函数添加一个基本情况并不能阻止它无限运行。该函数必须有一个步骤来使我们更接近基本情况。这就是递归步骤。在递归步骤中，问题被简化为问题的较小版本。

假设你有一个函数可以将从 n 开始的所有数字相乘。这称为阶乘函数，我们将其写为 4!，如果 n 等于 1。

在每个步骤中，你将从当前数字中减去 1。递归情况是什么？递归情况是函数 fact(4)。

16. 4 等于 1 吗？否。放入 fact(3)。
17. 3 等于 1 吗？否。放入 fact(2)。
18. 2 等于 1 吗？否。放入 fact(1)。
19. 1 等于 1 吗？是。返回 fact(2) 并返回 2。
20. 获取 3 * fact(2) 是 fact(4) 并返回 24。

这是另一种查看函数如何处理每个调用的方法：

<code>fact(4)
4 * fact(3)
4 * ( 3 * fact(2) )
4 * ( 3 * ( 2 * fact(1) ))
4 * ( 3 * ( 2 * 1 ) )
4 * ( 3 * 2 )
4 * 6
24</code>

在递归情况下，参数应该改变并使你更接近基本情况。应该在基本情况下测试此参数。在前面的示例中，因为我们在递归情况下减去 1，所以在基本情况下我们测试参数是否等于 0。

挑战

1. 使用循环而不是递归实现 sum 函数。
2. 创建一个递归地将两个数字相乘的函数。例如，0；否则，你返回数组的第一个元素加上 sum 调用。
3. 简化 filter 函数，使其从列表中删除所有项目的出现。例如，["a", "b", "d"]。

尾递归

尾递归是一种递归形式，它允许编译器执行尾调用优化 (TCO) 以防止普通递归的许多性能缺陷。此外，尾递归解决了函数调用最大深度的难题。但是，你必须以某种方式编写函数才能使其工作。

尾递归适用于在函数末尾调用递归函数的函数。例如，以下是 sum() 函数的尾递归版本：sum() 的整个返回值就是整个返回值，因此运行时可以安全地丢弃外部函数并只返回内部函数的结果。但是，许多人会被这样的事情绊倒：

function notTailRecursive(n) {
    // ...
    return notTailRecursive(n) 1
}

你可能认为这使用了尾递归，因为递归函数是在最后调用的。但是，它没有。这是因为 JavaScript 必须返回到外部函数才能加 1。你可以重写它的方法之一是将 1 传递到参数中，这样内部函数就可以进行该计算。

并非所有浏览器目前都支持尾调用优化，但它在 ES 标准中，因此我们将来可能会看到更多对它的支持。此外，它通常是一种很好的实践，因为它通常会隔离对函数参数的更改。

挑战

将本文中一个示例递归函数重构为尾递归函数。

总结

递归函数有三个部分。第一个是基本情况，它是终止条件。第二个是使我们更接近基本情况的步骤。第三个是递归步骤，其中函数使用简化的输入调用自身。

递归就像迭代。任何你可以递归定义的函数也可以使用循环来定义。使用递归时要考虑的其他事项包括递归嵌套列表和优化递归调用。

你可以将递归函数重构为尾递归函数，这可以提供性能优势。

一个继续学习递归的好资源是《The Little Schemer》这本书。它使用问答格式教你如何进行递归思考。

这篇文章已更新，其中包含 Jacob Jackson 的贡献。Jacob 是一位网络开发人员、技术作家、自由职业者和开源贡献者。

以上是使用JavaScript了解递归的详细内容。更多信息请关注PHP中文网其他相关文章！