功能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)

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

递归中的基本情况是阻止函数无限调用自身的条件。它至关重要，因为如果没有它，递归函数将无限地调用自身，导致堆栈溢出错误。基本情况通常是函数在进行递归调用之前检查的条件。如果满足该条件，则函数返回一个值并停止调用自身。

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

在JavaScript中，递归的工作原理是函数调用自身直到达到基本情况。该函数被划分为基本情况和递归情况。基本情况返回一个值而无需再次调用函数，而递归情况则使用不同的参数再次调用函数。该函数继续调用自身，直到达到基本情况，此时它开始返回值。

什么是JavaScript中的尾递归？

尾递归是一种特殊的递归，其中递归调用是函数中的最后一个操作。这很重要，因为它允许JavaScript引擎优化递归，使用一种称为尾调用优化的技术。这可以显著减少函数使用的内存量，使其能够处理更大的输入。

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

递归可以通过将复杂问题分解为更简单的问题来使代码更简洁易懂。它对于遍历树状数据结构等任务特别有用。但是，递归也可能不如迭代解决方案高效，如果实现不正确，可能会导致堆栈溢出错误。

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

当递归函数调用自身太多次，填满调用堆栈时，就会发生堆栈溢出错误。为避免这种情况，请确保您的递归函数具有最终将达到的基本情况。此外，请考虑使用尾递归，JavaScript引擎可以对其进行优化以使用更少的内存。

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

在函数式编程中，递归通常用作循环的替代品。由于函数式编程不鼓励使用可变状态，因此可以使用递归来执行重复操作而无需更改任何状态。

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

是的，理论上，所有递归函数都可以转换为迭代函数。但是，迭代版本可能更复杂且更难以理解，特别是对于涉及复杂树或图遍历的函数。

什么是JavaScript中的互递归？

互递归是指两个或多个函数以循环方式相互调用。这可能是解决某些类型问题的强大技术，但它也可能比简单的递归更难理解和调试。

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

由于重复的函数调用，调试递归函数可能具有挑战性。但是，使用console.log语句在每个步骤打印函数的参数和返回值可能会有所帮助。此外，使用允许您逐步执行函数调用的调试器工具非常有用。

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

是的，由于重复函数调用的开销，递归函数可能不如其迭代对应物高效。如果它们调用自身太多次，它们也可能导致堆栈溢出错误。但是，在许多情况下，递归解决方案的可读性和简单性可以超过这些性能方面的考虑。

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