JavaScript 中的递归和尾调用

如果你已经有一段时间的 JavaScript 开发经验,你很有可能会遇到递回这个定义,给定一个数字来阶乘,n! = n * (n - 1) * ... * 1 就是一个标准的递回例子。

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

上面所示的例子是阶乘函数最简单的实现。

为了更加完整的理解,我们来看看当 n = 6 时是如何运行的:

  • factorial(6)
    • 6 * factorial(5)
    • 5 * factorial (4)
      • 4 * factorial(3)
      • 3 * factorial(2)
        • 2 * factorial(1)
        • 1 * factorial(0)
          • 1
        • (恢复先前的执行) 1 * 1 = 1
        • (恢复…) 2 * 1 = 2
      • (…) 3 * 2 = 6
      • … 4 * 6 = 24
    • 5 * 24 = 120
    • 6 * 120 = 720
  • factorial(6) = 720

现在,我们必须非常小心的去了解发生了什么事,所以我们可以明白接下来会发生什么。

当我们调用一个函数时,会发生许多事。调用函数后必须保存返回的位置,以及当前的信息(即 n的值)。然后为新函数分配内存空间,并产生一个新的 frame(栈帧) 。

这是继续下去,我们继续堆叠这些 frame(栈帧),然后我们释放堆栈,用它们返回的值替换函数调用。

要注意的另一件事是,我们的 function 处理过程中产生的的形状。如果我将此形状叫做递归,您可能不会感到惊讶。因此,我们有一个递归过程。

我们来看看这个函数的第二个实现

function factorial(n, res) {
    if (n === 0) {
        return res;
    }
    return factorial(n - 1, res * n);
}

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

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);
}

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

  • factorial(6)
    • 使用 (n = 6, res = 1) 调用内部匿名函数 (iaf)
    • 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
  • factorial(6) = 720

您可能会注意到,展开堆栈后,我们不需要执行任何计算。我们只是返回一个值。但是,按照我们的规则,我们不得不将 state 储存为 frame(栈帧),即使它在这个中 chain 最后没有被任何的使用。

然而,我们的规则并不适用于所有语言。实际上,在 Scheme 中,这样的 chain 必须通过尾调用优化。这确保我们的 stack 不会被不必要的 frame(栈帧)填充。因此,我们先前的计算会看到这种方式︰

  • factorial(6)
  • iaf(6, 1)
  • iaf(5, 6)
  • iaf(4, 30)
  • iaf(3, 120)
  • iaf(2, 360)
  • iaf(1, 720)
  • iaf(0, 720)
  • 720

实上,看起来实在很像:

res = 1;
n = 6;

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

意思是,我们确实有一个反覆运算的处理,即使我们使用递归。这是多么酷啊?

好消息是 ES6 的 feature。只要你在尾递归调用,而且你的函数是 strict(严格) 模式,尾调用优化将储存并且踢除 maximum stack size exceeded 错误。

英文原文:

赞(0) 打赏
未经允许不得转载:WEBTian开发 » JavaScript 中的递归和尾调用

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

Tian开发相关广告投放 更专业 更精准

联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏