在 JavaScript 中利用尾递归来优化执行效率

发表于 2年以前 | 总阅读数：313 次

本文系“戏码台”原创，首发于 FCC 中文社区，感兴趣的小伙伴可以点击“阅读原文”前往 FCC 中文社区探索更多有意思的事情。如遇超链接无法使用，也请移步“阅读原文”呦。

递归是编程过程中常用的手段，跟许多初学者想象不同的是，我们使用递归，恰恰是因为递归的直觉性，能够很好的表达设计代码的逻辑思路，易于他人理解代码。

但是递归的代价也很明显，在Java中一个最典型的错误就是StackOverflowError，当你对一个factorial（阶乘）递归函数传入参数10000时，就可以遇到它了。

当然，在JavaScript也是会遇到类似的问题的。请看下面这段代码：

function factorial(n) {
    if (n < 2) {
        return 1;
    }
    return n * factorial(n - 1);
}

这就是一段非常典型的递归调用，可以算出n的阶乘。不加优化的情况下，这个函数会在执行的瞬间在内存中持有n份factorial函数的上下文，相应地我们就付出了n份内存的代价。显而易见，这样的程序在空间复杂度的考量上是极不友好的。同时，伴随着每次函数执行成功，返回、出栈，也会对CPU造成一定的压力。

因此，当我们在实战中真的遇到调用深度可能比较深的时候，要想办法避免传统的递归，而转而采用一种叫尾递归的方式来优化代码。

直接解释尾递归的概念的话，比较抽象。我们先来看用尾递归思路优化过后的代码：

function factorial(n, result = 1) {
    if (n < 2) {
        return result;
    }
    return factorial(n - 1, n * result);
}

这里我建议读者朋友们可以尝试在草稿纸上推导一下factorial(3)的执行过程，从而理解上面两种写法都是可以实现目的的。并且我在本文一开始也说了，递归的运用，其实是对程序逻辑的直观表达，更具可读性。这个在我们理解上面两段代码的逻辑时应该能有所体会。第一种写法应该是更好懂一些。

但是第二种写法是对机器极其友好的写法，因为它运用了尾递归，其执行速度就跟普通的循环没什么区别了，并且递归的深度也不受任何限制，也不用担心调用栈溢出或内存耗尽。

像上面第二种写法，在方法结束时出现的表达式，仅仅是自身的函数调用的递归，就是尾递归。

这里比较return n * factorial(n - 1);与return factorial(n - 1, n * result);就可以很好的看出来了，后者是一个纯粹的函数调用，而前者是在函数调用完后仍然做了其他运算。

那么为什么尾递归的执行效率更高呢？这其实是JavaScript解释器帮我们优化的结果。要理解这种优化，我们还需要引入另外一个概念——尾调用，先别着急头大。尾调用的概念更加简单些，维基百科里是这么解释的：

尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。

也就是上面的尾递归代码就是一种典型的尾调用，只是因为调用的函数也是自身，所以同时命中了递归的概念。其实JavaScript解释器之所以能够优化尾递归的执行效率，本质上是因为其对尾调用的优化。这种优化过程，说起来稍微有点绕，下面引用一段维基百科中的介绍帮助大家理解：

传统模式的编译器对于尾调用的处理方式就像处理其他普通函数调用一样，总会在调用时创建一个新的栈帧（stack frame）并将其推入调用栈顶部，用于表示该次函数调用。

当一个函数调用发生时，电脑必须 “记住” 调用函数的位置 —— 返回位置，才可以在调用结束时带着返回值回到该位置，返回位置一般存在调用栈上。在尾调用这种特殊情形中，电脑理论上可以不需要记住尾调用的位置而从被调用的函数直接带着返回值返回调用函数的返回位置（相当于直接连续返回两次）。尾调用消除即是在不改变当前调用栈（也不添加新的返回位置）的情况下跳到新函数的一种优化（完全不改变调用栈是不可能的，还是需要校正调用栈上形式参数与局部变量的信息。）

由于当前函数帧上包含局部变量等等大部分的东西都不需要了，当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用，然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 “jump”（而不是一般常规函数调用的代码）的过程称作尾调用消除(Tail Call Elimination)或尾调用优化(Tail Call Optimization, TCO)。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高，也因此使得高效的结构编程成为现实。

如果你想了解具体JavaScript是怎么操作的，还可以阅读《JavaScript悟道》这本书的第143页。

对于初学者来说，理解不了上面复杂的优化概念也没有关系。我们需要了解的第一是递归的写法和应用场景，第二要明白递归是有代价的，不宜过深，第三就是在合适的时候通过尾递归的方式优化递归函数的执行效率。只需要牢记这三点就足够了。