javascript尾调用

标签（空格分隔）： javascript

尾调用(Tail Call)

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

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

在 f 函数中，最后一步操作是调用 g 函数，并且调用 g 函数的返回值被 f 函数直接返回，这就是尾调用。而下面这个栗子就不是尾调用：

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

原因是它的最后一步操作是将 g 函数调用的返回值和 1 进行加法操作，而不是调用其他函数，所以它不是尾调用。

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

[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

才到第 5 项调用栈长度就有 8 了，一些复杂点的递归稍不注意就会超出限度，同时也会消耗大量内存。而如果用尾递归的方式来优化这个过程，就可以避免这个问题，用尾递归来求 Fibonacci 数列的值可以写成这样：

function fibonacciTail(n, a = 0, b = 1) {  
  if (n === 0) return a  return fibonacciTail(n - 1, b, a + b)}

在这里，每次调用后递归传入 fibonacciTail 函数的 n 会依次递减 1，它实际上是用来记录递归剩余的次数。而 a 和 b 两个参数在每次递归时也会在计算后再次传入 fibonacciTail 函数，写成调用栈的形式就很清楚了：

fibonacciTail(5) === fibonacciTail(5, 0, 1)  
fibonacciTail(4, 1, 1)  
fibonacciTail(3, 1, 2)  
fibonacciTail(2, 2, 3)  
fibonacciTail(1, 3, 5)  
fibonacciTail(0, 5, 8) => return 5

可以看到，每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧而已。也就避免了内存的浪费和爆栈的危险。

注意

很多介绍尾调用和尾递归的文章讲到这里就结束了，实际上情况并非这么简单，尾调用在没有进行任何优化的时候和其他的递归方式一样，该产生的调用栈一样会产生，一样会有爆栈的危险。而尾递归之所以可以优化，是因为每次递归调用的时候，当前作用域中的局部变量都没有用了，不需要层层增加调用栈再在最后层层回收，当前的调用帧可以直接丢弃了，这才是尾调用可以优化的原因。

由于尾递归是尾调用的一种特殊形式，相对简单一些，在 ES6 没有开启尾调用优化的时候，我们可以手动为尾递归做一些优化。

尾递归优化

改写为循环

之所以需要优化，是因为调用栈过多，那么只要避免了函数内部的递归调用就可以解决掉这个问题，其中一个方法是用循环代替递归。还是以 Fibonacci 数列举例：

function fibonacciLoop(n, a = 0, b = 1) {  
  while (n--) {
    [a, b] = [b, a + b]
  }
  return a;
  }

这样，不存在函数的多次调用，将递归转变为循环，避免了调用栈的无限增加。

蹦床函数

另一个优化方法是借助一个蹦床函数的帮助，它的原理是接受一个函数作为参数，在蹦床函数内部执行函数，如果函数的返回是也是一个函数，就继续执行。

function trampoline(f) {  
  while (f && f instanceof Function) {
    f = f()
  }
  return f
  }

可以看到，这里也没有在函数内部调用函数，而是在循环中重复调用同一个函数，这也避免了增加调用栈长度，下面要做的是将原来的 Fibonacci 函数改写为每次返回另一个函数的版本：

function fibonacciFunc(n, a = 0, b = 1) {  
  if (n > 0) {
    [a, b] = [b, a + b]
    return fibonacciFunc.bind(null, n - 1, a, b)
  } else {
    return a  }}trampoline(fibonacciFunc(5)) // return 5

实际的尾递归优化

实际上，真正的尾递归优化并非像上面一样，上面的两种方法实际上都改写了尾递归函数本身，而真正的尾递归优化应该是非入侵式的，下面是尾递归优化的一种实现：

function tailCallOptimize(f) {  
  let value,
      active = false
  const accumulated = []
  return function accumulator() {
    accumulated.push(arguments)
    if (!active) {
      active = true
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift())
      }
      active = false
      return value    }
  }}

然后将原来的 fibonacciTail 函数传入 tailCallOptimize 函数，得到一个新函数，这个新函数的执行过程就是经过尾递归优化的了：

const fibonacciTail = tailCallOptimize(function(n, a = 0, b = 1) {  
  if (n === 0) return a  return fibonacciTail(n - 1, b, a + b)})fibonacciTail(5) // return 5

下面解释一下这种优化方式的原理。

1. 首先通过闭包，在 tailCallOptimize 的作用域中保存唯一的 active 和 accumulated，其中 active 指示尾递归优化过程是否开始，accumulated 用来存放每次递归调用的参数，push 方法将参数入列，shift 方法将参数出列，保证先进先出顺序执行。
2. 经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 fibonacciTail 时实际执行的是这个函数，第一次执行时，现将 arguments0 推入队列，active 会被标记为 true，然后进入 while 循环，取出 arguments0。在 while 循环的执行中，会将参数类数组 arguments1 推入 accumulated 队列，然后直接返回 undefined，不会递归调用增加调用栈。
3. 随后 while 循环会发现 accumulated 中又多了一个 arguments1，然后再将 arguments2推入队列。这样，在 while 循环中对 accumulated 的操作就是放进去一个、拿出来一个、再放进去一个、再拿出来一个，以此类推。
4. 最后一次 while 循环返回的就是尾递归的结果了。

问题

实际上，现在的尾递归优化在引擎实现层面上还是有问题的。拿 V8 引擎来说，尾递归优化虽然已经实现了，但默认是不开启的，V8 团队还是更倾向于用显式的语法来优化。原因是在他们看来，尾调用优化仍然存在一些问题，主要有两点：

难以辨别

在引擎层面消除尾递归是一个隐式行为，函数是不是符合尾调用的要求，可能程序员在写代码的时候不会意识到，另外由于开启了尾调用优化，一旦出现了死循环尾递归，又不会引发溢出，难以辨别。下面介绍一些识别尾调用要注意的地方：

首先，调用函数的方式不重要，以下几种调用方式只要出现在尾调用位置上都可以被优化： + 普通调用：func(...) + 作为方法调用：obj.method(...) + 使用 call 或 apply 调用：func.call(..) 或 func.apply(...)

表达式中的尾调用

ES6 的箭头函数可以使用一个表达式作为自己的函数体，函数返回值就是这个表达式的返回值，在表达式中，以下几种情况可能包含尾调用：
三元运算符(? :)

const a = x => x ? f() : g()

在这里，f 和 g 函数都在尾调用位置上。为了便于理解，可以将函数改写一下：

const a = x => {  
  if (x) {
    return f()
  } else {
    return g()
  }}

可见 f 和 g 的返回值都是直接被返回的，符合尾调用的定义。

逻辑运算符（|| 与 &&） 首先是 || 运算符：

const a = () => f() || g()

这里 f 函数不在尾递归位置上，而 g 函数在尾递归位置上，为什么，把函数改写一下就清楚了：

const a = () => {  
  const result = f()
  if (result) {
    return result  } else {
    return g()
  }}

|| 运算符的结果依赖于 f 函数的返回值，而不是直接返回 f 的返回值，直接返回的只有 g 函数的返回值。&& 运算符的情况也同理：

const a = () => f() && g()

将函数改写为：

const a = () => {  
  const result = f()
  if (!result) {
    return result  } else {
    return g()
  }}

说明 f 函数也不在尾递归位置上，而 g 函数在尾递归位置上。

逗号运算符（,）

const a = () => (f(), g())

将函数改写一下：

const a = () => {  
  f()
  return g()}

可见，在尾递归位置上的仍然只有一个 g 函数。

语句中的尾调用
在 JS 语句中，以下几种情况可能包含尾调用： + 代码块中（由 {} 分隔的语句） + if语句的 then 或 else 块中 + do-while，while，for 循环的循环体中 + switch 语句的执行代码块中 + try-catch 语句的 catch 块中 + try-finally，try-catch-finally 语句的 finally 块中

此外，return 语句也可以包含尾调用，如果 return 的表达式包含尾调用，return 语句就包含尾调用，这就不用多解释了。

单独的函数调用不是尾调用

下面这个函数是否包含尾调用呢：

function foo() {  
  bar()}

答案是否定的，还是先将函数改写一下：

function foo() {  
  bar()
  return undefined
  }

可以看到 return 语句返回的只是一个 undefined 而并非 bar 函数的返回值，所以这里不存在尾调用。

尾调用只能出现在严格模式中
在非严格模式中，大多数引擎会在函数上增加下面两个属性： + func.arguments 包含调用函数时传入的参数 + func.caller 返回当前函数的调用者

但一旦进行了尾调用优化，中间调用帧会被丢弃，这两个属性也就失去了本来的意义，这也是在严格模式中不允许使用这两个属性的原因。

堆栈信息丢失
除了开发者难以辨别尾调用以外，另一个原因则是堆栈信息会在优化的过程中丢失，这对于调试是不方便的，另外一些依赖于堆栈错误信息来进行用户信息收集分析的工具可能会失效。针对这个问题，实现一个影子堆栈可以解决堆栈信息缺失的问题，但这中解决方式相当于对堆栈进行了模拟，不能保证始终符合实际虚拟机堆栈的真实状态。另外，影子堆栈的性能开销也是非常大的。

基于以上原因，V8 团队建议使用特殊的语法来指定尾递归优化，TC39 标准委员会有一个还没有结论的提案叫做从语法上指定尾部调行为，这个提案由来自 Mozilla 和微软的委员提出。提案的具体内容可以看链接，主要是提出了三种手动指定尾调用优化的语法。

附手动优化语法

Return Continue
function factorial(n, acc = 1) {  
  if (n === 1) {
    return acc;
  }
 return continue factorial(n - 1, acc * n)}
let factorial = (n, acc = 1) => continue  
  n == 1 ? acc: factorial(n - 1, acc * n);// or, if continue is an expression form:
let factorial = (n, acc = 1) =>  
  n == 1 ? acc: continue factorial(n - 1, acc * n);
Function sigil
// # sigil, though it's already 'claimed' by private state.
#function() { /* all calls in tail position are tail calls */ }
// Note that it's hard to decide how to readably sigil arrow functions.
// This is probably most readable.() 
#=> expr
// This is probably most in line with the non-arrow sigil.
#() => expr
// rec sigil similar to async functions
rec function() { /* likewise */ }  
rec () => expr  
!-return
function () { !return expr }

// It's a little tricky to do arrow functions in this method.
// Obviously, we cannot push the ! into the expression, and even
// function level sigils are pretty ugly.
// Since ! already has a strong meaning, it's hard to read this as
// a tail recursive function, rather than an expression.
!() => expr
// We could do like we did for # above, but it also reads strangely:() 
!=> expr