学习下JS中的递归和尾调用

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

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

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

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

• factorial(6)

• 4 * factorial(3)

• 3 * factorial(2)

• (…) 3 * 2 = 6

• … 4 * 6 = 24

• 1

• 2 * factorial(1)

• 1 * factorial(0)

• (恢复先前的执行) 1 * 1 = 1

• (恢复…) 2 * 1 = 2

• 6 * factorial(5)

• 5 * factorial (4)

• 5 * 24 = 120

• 6 * 120 = 720

• factorial(6) = 720

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

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

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

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

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

JavaScript 代码:

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

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

JavaScript 代码:

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)

• iaf(4, 6 * 5)

• iaf(3, 30 * 4)

• 720

• 720

• iaf(0, 720)

• 720

• 720

• iaf(2, 120 * 3)

• iaf(1, 360 * 2)

• 720

• 720

• 使用 (n = 6, res = 1) 调用内部匿名函数 (iaf)

• iaf(5, 1 * 6)

• 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

实上，看起来实在很像：

JavaScript 代码:

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

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

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