JavaScript

JavaScript 中的递归，迭代和尾部调用

Posted by cl9000 on May 21, 2020

预测未来最好的方法就是去创造未来。——<亚伯拉罕·林肯>

递归的定义

给定数字的阶乘 n! = n * (n - 1) * ... * 1 是标准示例。

1
2
3
4
5
6
function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

上面显示的示例只是阶乘函数的最幼稚实现。

为了完整起见，让我们看一下它是如何执行的 n = 6：

  • 阶乘（6）
    • 6 *阶乘（5）
      • 5 *阶乘（4）
        • 4 *阶乘（3）
          • 3 *阶乘（2）
            • 2 *阶乘（1）
              • 1 *阶乘（0）
                • 1个
              • （恢复先前的执行）1 * 1 = 1
            • （正在恢复…）2 * 1 = 2
          • （…）3 * 2 = 6
        • …4 * 6 = 24
      • 5 * 24 = 120
    • 6 * 120 = 720
  • 阶乘（6）= 720

现在，我们必须对正在发生的事情非常谨慎，这样我们才能了解接下来会发生什么。

当我们调用一个函数时，会同时发生几件事。保存了调用函数后必须返回的位置以及当前帧的信息（即n的值）。然后为新功能分配空间，并诞生一个新的框架。

如此反复，我们继续堆叠这些帧，然后展开该堆叠，用函数返回的值替换函数调用。

还要注意的另一件事是我们的函数所生成的过程的形状。如果我将此形状称为递归，您可能不会感到惊讶。因此，我们有一个 递归过程。

让我们看一下该函数的第二种实现。

1
2
3
4
5
6
function factorial(n, res) {
    if (n === 0) {
        return res;
    }
    return factorial(n - 1, res * n);
}

我们可以通过定义内部函数来进一步封装功能。

1
2
3
4
5
6
7
8
9
function factorial(n) {
    function inner_factorial(n, res) {
        if (n === 0) {
            return res;
        }
        return inner_factorial(n - 1, res * n);
    }
    return inner_factorial(n, 1);
}

让我们看一下它是如何执行的：

  • 阶乘（6）
    • 内部匿名函数（iaf）被调用（n = 6，res = 1）
      • iaf（5，1 * 6）
        • iaf（4，6 * 5）
          • iaf（3，30 * 4）
            • iaf（2，120 * 3）
              • iaf（1，360 * 2）
                • iaf（0，720）
                  • 720
                • 720
              • 720
            • 720
          • 720
        • 720
      • 720
    • iaf（6，1）= 720
  • 阶乘（6）= 720

您可能会注意到，展开堆栈后，我们不需要执行任何计算。我们刚刚返回了一个值。但是，根据我们的规则，即使状态链后面没有任何用处，我们也必须将状态保存为堆栈框架。

但是，我们的规则并不适用于所有语言。实际上，在Scheme中，必须通过尾部调用优化来优化此类链。这样可以确保我们的堆栈不会充满不必要的框架。因此，我们以前的计算看起来像这样：

  • 阶乘（6）
  • iaf（6，1）
  • iaf（5，6）
  • iaf（4、30）
  • iaf（3，120）
  • iaf（2，360）
  • iaf（1，720）
  • iaf（0，720）
  • 720

反过来看起来非常像

1
2
3
4
5
6
7
res = 1;
n = 6;

while(n > 1) {
    res = res * n;
    n--;
}

意味着，即使我们正在使用递归，我们实际上也有一个迭代过程。多么酷啊？

好消息是，这是ES6的功能。只要您的递归调用处于尾部位置并且您的函数具有严格模式，尾部调用优化就会开始执行，并避免出现maximum stack size exceeded错误。

参考

关注【公众号】，了解更多。


赏 支付宝打赏 微信打赏

赞赏一下 坚持原创技术分享，您的支持将鼓励我继续创作！



FEATURED TAGS
JavaScript
FRIENDS