es6学习笔记 尾递归优化

Posted on | In ,

前言

之前也有一直接触尾递归这个概念，可是最近才发现其实在JavaScript中尾递归优化并不是默认支持的。其实这个概念一直在书上有，但一不小心忽略了+ +..在ES6中才第一次明确规定，所有ECMAScript的实现都必须部署“尾调用优化”，可是es6只是一个标准规范，在不同运行环境的支持程度也不一样，我在本机Chrome(70.0.3538.67)上测试也还是会爆栈。

实际上大多数浏览器都不支持尾递归优化，详情可以看这里。

在node6.5+版本中使用 –harmony-tailcalls关键字可以运行
node --harmony-tailcalls test.js

尾递归优化只在es6的严格模式下开启

ES6的尾调用优化只在严格模式下开启，正常模式下是无效的。
这是因为，在正常模式下函数内部有两个变量，可以跟踪函数的调用栈。

  • func.arguments
  • func.caller 但会调用当前函数的那个函数
    尾调用优化发生时，函数的调用栈会改写，因此上面两个变量会失真。严格模式禁用这两个变量，所有尾调用模式尽在严格模式下生效。

如何在正常模式下/不支持优化的环境中实现尾递归优化

蹦床函数

比如下面这个递归函数

1
2
3
4
5
function sum(x,y){
  if(y>0) return sum(x+1,y-1)
  else return x
}
sum(1,100000) // 报错：爆栈

我们可以使用蹦床函数(trampoline)可以将递归执行转为循环执行。

1
2
3
4
5
6
function trampoline(f){
  while(f && f instanceof Function){
    f=f()
  }
  return f
}

在上述函数中接收函数f作为参数。只要f执行后返回一个函数就可以继续执行。
该函数的实现是返回一个函数然后执行该函数，而不是在函数中调用函数，这样就避免了递归执行，从而消除了调用栈过大的问题。
现在我们再来改写一下递归函数sum

1
2
3
4
function sum(x,y){
  if(y > 0) return sum.bind(null,x+1,y-1) // 每次执行都会返回自身的另一个版本
  else return x
}

改写了的sum函数中，每次执行都会返回自身的另一个版本（即返回函数而非调用函数），而不是递归调用自己。

1
trampoline(sum(1,100000)) // 此时就不会发生调用栈溢出了

tco函数：真正的尾递归优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function tco(f){
  var value;
  var active = false;
  var accumulated= [];
  return function accumulator(){
    accumulated.push(arguments);
    if(!active){
      active=true;
      while(accumulated.length){
        value=f.apply(this,accumulated.shift())
      }
      active=false;
      return value;
    }
  }
}
var sum=tco(function(x,y){
  if(x>0)return sum(x+1,y-1)
  else return x
})
sum(1,100000)

上述代码中，tco函数是尾递归优化的实现，它的奥妙就在于状态标量active。默认情况下，这个变量是不被集火的。一旦进入尾递归优化的过程，这个变量就被激活了。可是在while循环里面感觉好像也是在递归啊？既然他是一个优化函数，那么答案很明显不是:) 那我们来努力理解一下这个函数吧~

  • 首先以函数表达式的形式将tco函数的返回值赋给sum，tco函数的返回值是accumulator函数，也就是说当执行sum(1,10)的时候即是在执行accumulator(1,10)，要牢记这一点
  • 在tco函数中accumulator就是一个闭包，可以自由访问active、value和accumulated数组
  • 上面我们说到执行sum函数也就是执行accumulator函数，那么第一次的参数(1,100000)也就变成了accumulator函数的arguments，accumulate数组作用就是push每一次sum(accumulator)函数的参数
  • 此时active为false，所以接下来我们进入while循环。
  • 在while循环中我们把tco函数中f函数赋值给了value值，而此时f函数的返回值是一个sum立即执行函数，好了，还记得上面我们说的吗，执行sum函数也就是执行accumulator函数。
  • 此时，再次进入accumulator函数，并把第二个sum函数的参数push进accumulate数组中。而因为我们在第一个执行accumulator函数的时候，已经把active标记为true，而accumulator函数是一个闭包函数，共享一个active，所以此时我们并不会进入if块，也就是我们执行了第一条语句accumulated.push(arguments);
  • 换而言之，f函数(即tco形参)中不停地调用sum函数，其实都只是执行了第一条语句accumulated.push(arguments);，所以value值一直都是被赋值为undefined，可是因为accumulated数组一直被push进新的参数，所以while循环一直再继续；直至f函数不再调用sum而是返回x时，accumulated数组也就为空了，value的最后的值就是f函数中else块所返回的x，则此时x的值就赋给了value并return出来了。

所以综上，tco函数的原理其实还是采用了将递归改成了循环，而后一轮的参数会去掉前一轮的参数，保证了调用栈只有一层。

参考链接

《ES6标准入门》 阮一峰著
JS的递归与TCO尾调用优化
sec-tail-position-calls