功能JavaScript中的递归-js教程-PHP中文网

递归中的基本情况是什么？为什么它很重要？

递归在JavaScript中是如何工作的？

什么是JavaScript中的尾递归？

使用JavaScript中的递归的优点和缺点是什么？

如何避免递归函数中的堆栈溢出错误？

递归在函数式编程中是如何使用的？

所有递归函数都可以转换为迭代函数吗？

什么是JavaScript中的互递归？

如何调试JavaScript中的递归函数？

使用递归时是否存在任何性能方面的考虑？

首页

web前端

js教程

功能JavaScript中的递归

Joseph Gordon-Levitt

Feb 19, 2025 am 10:22 AM

Recursion in Functional JavaScript

JavaScript中的递归函数或许你已经听说过，甚至尝试编写过一些。但你可能没见过很多实际有效的递归示例。事实上，除了这种方法的特殊性之外，你可能还没有考虑过递归何时何地有用，或者如果使用不当会多么危险。

要点

递归是一种JavaScript方法，允许函数重复调用自身，直到达到结果。它对于涉及迭代分支的问题特别有用，例如分形数学、排序或遍历复杂或非线性的数据结构。
虽然递归可以使代码更简洁易懂，但如果使用不当，由于存在超过引擎内存容量的风险，它可能是危险的。这是因为JavaScript递归函数需要每次都跟踪它们从何处被调用，以便它们能够在正确的位置继续执行。
在许多函数式编程语言中，一种称为尾调用优化的技术用于管理递归。这允许递归函数中的每个连续循环立即发生，而不是堆积在内存中。但是，大多数JavaScript编译器目前尚未针对此进行优化。
可以构建自定义弹跳函数来迭代地管理递归执行，一次只在堆栈上保留一个操作。这可以帮助避免创建等待执行的深度堆栈操作，但通常是以牺牲性能和可读性为代价的。

递归的用途

递归是一种通过让函数重复调用自身直到得到结果来迭代操作的技术。大多数循环都可以用递归样式重写，在某些函数式编程语言中，这种循环方法是默认的。

但是，虽然JavaScript的函数式编程风格支持递归函数，但我们需要意识到大多数JavaScript编译器目前还没有针对它们进行安全优化。

当需要在循环中使用不同的参数重复调用同一个函数时，最好使用递归。虽然它可以用于许多情况，但它最有效的是解决涉及迭代分支的问题，例如分形数学、排序或遍历复杂或非线性的数据结构的节点。

递归在函数式编程语言中受到青睐的一个原因是，它允许构建不需要使用局部变量设置和维护状态的代码。递归函数也很容易测试，因为它们很容易以纯净的方式编写，对于任何给定的输入都有一个特定且一致的返回值，并且不会对外部变量状态产生副作用。

循环

递归可以应用的一个经典函数示例是阶乘。这是一个函数，它返回一个数字反复乘以每个前一个整数的结果，一直到1。

例如，3的阶乘是：

<code>3 × 2 × 1 = 6</code>

登录后复制

6的阶乘是：

<code>3 × 2 × 1 = 6</code>

登录后复制

你可以看到这些结果有多快就变大了。你还可以看到我们一遍又一遍地重复相同的行为。我们取一个乘法运算的结果，再乘以第二个值减1。然后我们一次又一次地这样做，直到达到1。

使用for循环，创建迭代执行此操作直到返回正确结果的函数并不困难：

<code>6 × 5 × 4 × 3 × 2 × 1 = 720</code>

登录后复制

这有效，但从函数式编程的角度来看，它并不优雅。为了支持for循环然后返回结果，我们必须使用几个维护和跟踪状态的局部变量。如果我们可以丢弃for循环，并采用更函数式的JavaScript方法，岂不是更简洁？

递归

我们知道JavaScript允许我们编写将函数作为参数的函数。那么，如果我们想使用我们正在编写的实际函数并在运行它的上下文中执行它呢？

这甚至可能吗？当然可以！例如，考虑这样一个简单的while循环：

var factor = function(number) {
  var result = 1;
  var count;
  for (count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6));
// 720

登录后复制

完成此操作后，counter的值已更改，但循环已完成其打印每个值的作业，因为我们缓慢地从其中提取了状态。

相同循环的递归版本可能更像这样：

var counter = 10;
while(counter > 0) {
    console.log(counter--);
}

登录后复制

你看到我们如何在countdown函数的定义中直接调用countdown函数了吗？JavaScript像老板一样处理它，并且只做你希望它做的事情。每次执行countdown时，JavaScript都会跟踪它从何处被调用，然后回溯到该函数调用的堆栈，直到完成。我们的函数也避免了修改任何变量的状态，但仍然利用传入的值来控制递归。

回到我们的阶乘案例，我们可以这样重写之前的函数以使用递归：

var countdown = function(value) {
    if (value > 0) {
        console.log(value);
        return countdown(value - 1);
    } else {
        return value;
    }
};
countdown(10);

登录后复制

以这种方式编写代码允许我们以无状态的方式描述整个过程，没有任何副作用。同样值得注意的是，我们首先测试传递给函数的参数的值，然后再进行任何计算。我们希望任何将要调用自身的函数在到达其终止情况时都能快速干净地退出。对于以这种方式计算的阶乘，当传入的数字为零或负数时，会到达终止情况（如果我们希望，我们也可以测试负值并返回不同的消息）。

尾调用优化

当代JavaScript实现的一个问题是，它们没有标准的方法来防止递归函数无限地堆积自身，并消耗内存直到超过引擎的容量。JavaScript递归函数需要每次都跟踪它们从何处被调用，以便它们能够在正确的位置继续执行。

在许多函数式编程语言（如Haskell和Scheme）中，这是使用称为尾调用优化的技术来管理的。使用尾调用优化，递归函数中的每个连续循环将立即发生，而不是堆积在内存中。

理论上，尾调用优化是ECMAScript 6（当前JavaScript的下一个版本）标准的一部分，但是大多数平台尚未完全实现它。

弹跳函数

如有必要，有一些方法可以强制JavaScript以安全的方式执行递归函数。例如，可以构建自定义弹跳函数来迭代地管理递归执行，一次只在堆栈上保留一个操作。以这种方式使用的弹跳函数可以利用JavaScript将函数绑定到特定上下文的能力，以便将递归函数弹回自身，一次构建一个结果，直到循环完成。这将避免创建等待执行的深度堆栈操作。

实际上，使用弹跳函数通常会为了安全而降低性能。此外，我们通过以递归方式编写函数获得的大部分优雅性和可读性都会在使这种方法在JavaScript中起作用所需的代码卷积中丢失。

如果你好奇，我鼓励你阅读更多关于这个概念的信息，并在下面的讨论中分享你的想法。你可以从StackOverflow上的一个简短主题开始，然后探索Don Taylor和Mark McDonnell的一些文章，这些文章更深入地探讨了JavaScript中弹跳函数的优缺点。

我们还没到那一步

递归是一项强大的技术，值得了解。在许多情况下，递归是解决复杂问题的最直接方法。但是，在ECMAScript 6在我们需要的地方用尾调用优化完全实现之前，我们需要非常小心地应用递归的方式和位置。

关于函数式JavaScript中递归的常见问题解答 (FAQs)