深入理解JavaScript中的尾调用(Tail Call)

什么是尾调用？

尾调用是函数式编程里比较重要的一个概念，尾调用的概念非常简单，一句话就能说清楚，它的意思是在函数的执行过程中，如果最后一个动作是一个函数的调用，即这个调用的返回值被当前函数直接返回，则称为尾调用，如下所示：

function f(x) {  return g(x)}

在 f 函数中，最后一步操作是调用 g 函数，并且调用 g 函数的返回值被 f 函数直接返回，这就是尾调用。

而下面两种情况就不是尾调用：

// 情况一function f(x){ let y = g(x); return y;}// 情况二function f(x){ return g(x) + 1;}

上面代码中，情况一是调用函数g之后，还有别的操作，所以不属于尾调用，即使语义完全一样。情况二也属于调用后还有操作，即使写在一行内。。

为什么说尾调用重要呢，原因是它不会在调用栈上增加新的堆栈帧，而是直接更新调用栈，调用栈所占空间始终是常量，节省了内存，避免了爆栈的可能性。用上面的栗子来说，尾调用的调用栈是这样的：

[f(x)] => [g(x)]

由于进入下一个函数调用时，前一个函数内部的局部变量（如果有的话）都不需要了，那么调用栈的长度不会增加，可以直接跳入被尾调用的函数。如果是非尾调用的情况下，调用栈会长这样：

[f(x)] => [1 + g(x)]

可以看到，调用栈的长度增加了一位，原因是 f 函数中的常量 1 必需保持保持在调用栈中，等待 g 函数调用返回后才能被计算回收。如果 g 函数内部还调用了函数 h 的话，就需要等待 h 函数返回，以此类推，调用栈会越来越长。如果这样解释还不够直观的话，尾调用还有一种特殊情况叫做尾递归，它的应用更广，看起来也更直观。

尾递归

顾名思义，在一个尾调用中，如果函数最后的尾调用位置上是这个函数本身，则被称为尾递归。递归很常用，但如果没写好的话也会非常消耗内存，导致爆栈。一般解释递归会用阶乘或者是斐波那契数列求和作为示例，这里用后者来解释一下。Fibonacci 数列就不多做解释了，它是一个长这样的无限长的数列，从第三项开始，每项都是前两项的和：

0, 1, 1, 2, 3, 5, 8, 13, 21, ... 

如果要计算第 n 项（从第 0 项开始）的值的话，写成递归是常用的手段。如果是非尾递归的形式，可以写成这样：

function fibonacci(n) {  if (n === 0) return 0 if (n === 1) return 1 return fibonacci(n - 1) + fibonacci(n - 2)}

以 n = 5 来说，fibonacci 函数的调用栈会像这样展开：

[fibonacci(5)][fibonacci(4) + fibonacci(3)][(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))][((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))][fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)][1 + 0 + 1 + 1 + 0 + 1 + 0 + 1]5