深入理解JavaScript中的尾调用(Tail Call)
什么是尾调用？
尾调用是函数式编程里比较重要的一个概念，尾调用的概念非常简单，一句话就能说清楚，它的意思是在函数的执行过程中，如果最后一个动作是一个函数的调用，即这个调用的返回值被当前函数直接返回，则称为尾调用，如下所示：
functionf(x){
returng(x)
}
在f函数中，最后一步操作是调用g函数，并且调用g函数的返回值被f函数直接返回，这就是尾调用。
而下面两种情况就不是尾调用：
//情况一
functionf(x){
lety=g(x);
returny;
}
//情况二
functionf(x){
returng(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项开始）的值的话，写成递归是常用的手段。如果是非尾递归的形式，可以写成这样：
functionfibonacci(n){
if(n===0)return0
if(n===1)return1
returnfibonacci(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数列的值可以写成这样：
functionfibonacciTail(n,a=0,b=1){
if(n===0)returna
returnfibonacciTail(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)=>return5
可以看到，每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧而已。也就避免了内存的浪费和爆栈的危险。
注意
很多介绍尾调用和尾递归的文章讲到这里就结束了，实际上情况并非这么简单，尾调用在没有进行任何优化的时候和其他的递归方式一样，该产生的调用栈一样会产生，一样会有爆栈的危险。而尾递归之所以可以优化，是因为每次递归调用的时候，当前作用域中的局部变量都没有用了，不需要层层增加调用栈再在最后层层回收，当前的调用帧可以直接丢弃了，这才是尾调用可以优化的原因。
由于尾递归是尾调用的一种特殊形式，相对简单一些，在ES6没有开启尾调用优化的时候，我们可以手动为尾递归做一些优化。
尾递归优化
改写为循环
之所以需要优化，是因为调用栈过多，那么只要避免了函数内部的递归调用就可以解决掉这个问题，其中一个方法是用循环代替递归。还是以Fibonacci数列举例：
functionfibonacciLoop(n,a=0,b=1){
while(n--){
[a,b]=[b,a+b]
}
returna
}
这样，不存在函数的多次调用，将递归转变为循环，避免了调用栈的无限增加。
蹦床函数
另一个优化方法是借助一个蹦床函数的帮助，它的原理是接受一个函数作为参数，在蹦床函数内部执行函数，如果函数的返回是也是一个函数，就继续执行。
functiontrampoline(f){
while(f&&finstanceofFunction){
f=f()
}
returnf
}
可以看到，这里也没有在函数内部调用函数，而是在循环中重复调用同一个函数，这也避免了增加调用栈长度，下面要做的是将原来的Fibonacci函数改写为每次返回另一个函数的版本：
functionfibonacciFunc(n,a=0,b=1){
if(n>0){
[a,b]=[b,a+b]
returnfibonacciFunc.bind(null,n-1,a,b)
}else{
returna
}
}
trampoline(fibonacciFunc(5))//return5
实际的尾递归优化
实际上，真正的尾递归优化并非像上面一样，上面的两种方法实际上都改写了尾递归函数本身，而真正的尾递归优化应该是非入侵式的，下面是尾递归优化的一种实现：
functiontailCallOptimize(f){
letvalue,
active=false
constaccumulated=[]
returnfunctionaccumulator(){
accumulated.push(arguments)
if(!active){
active=true
while(accumulated.length){
value=f.apply(this,accumulated.shift())
}
active=false
returnvalue
}
}
}
然后将原来的fibonacciTail函数传入tailCallOptimize函数，得到一个新函数，这个新函数的执行过程就是经过尾递归优化的了：
constfibonacciTail=tailCallOptimize(function(n,a=0,b=1){
if(n===0)returna
returnfibonacciTail(n-1,b,a+b)
})
fibonacciTail(5)//return5
下面解释一下这种优化方式的原理。
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的箭头函数可以使用一个表达式作为自己的函数体，函数返回值就是这个表达式的返回值，在表达式中，以下几种情况可能包含尾调用：
三元运算符(?:)
consta=x=>x?f():g()
在这里，f和g函数都在尾调用位置上。为了便于理解，可以将函数改写一下：
consta=x=>{
if(x){
returnf()
}else{
returng()
}
}
可见f和g的返回值都是直接被返回的，符合尾调用的定义。
逻辑运算符（||与&&）
首先是||运算符：
consta=()=>f()||g()
这里f函数不在尾递归位置上，而g函数在尾递归位置上，为什么，把函数改写一下就清楚了：
consta=()=>{
constresult=f()
if(result){
returnresult
}else{
returng()
}
}
||运算符的结果依赖于f函数的返回值，而不是直接返回f的返回值，直接返回的只有g函数的返回值。&&运算符的情况也同理：
consta=()=>f()&&g()
将函数改写为：
consta=()=>{
constresult=f()
if(!result){
returnresult
}else{
returng()
}
}
说明f函数也不在尾递归位置上，而g函数在尾递归位置上。
逗号运算符（,）
consta=()=>(f(),g())
将函数改写一下：
consta=()=>{
f()
returng()
}
可见，在尾递归位置上的仍然只有一个g函数。
语句中的尾调用
在JS语句中，以下几种情况可能包含尾调用：+代码块中（由{}分隔的语句）+if语句的then或else块中+do-while，while，for循环的循环体中+switch语句的执行代码块中+try-catch语句的catch块中+try-finally，try-catch-finally语句的finally块中
此外，return语句也可以包含尾调用，如果return的表达式包含尾调用，return语句就包含尾调用，这就不用多解释了。
单独的函数调用不是尾调用
下面这个函数是否包含尾调用呢：
functionfoo(){
bar()
}
答案是否定的，还是先将函数改写一下：
functionfoo(){
bar()
returnundefined
}
可以看到return语句返回的只是一个undefined而并非bar函数的返回值，所以这里不存在尾调用。
尾调用只能出现在严格模式中
在非严格模式中，大多数引擎会在函数上增加下面两个属性：+func.arguments包含调用函数时传入的参数+func.caller返回当前函数的调用者
但一旦进行了尾调用优化，中间调用帧会被丢弃，这两个属性也就失去了本来的意义，这也是在严格模式中不允许使用这两个属性的原因。
堆栈信息丢失
除了开发者难以辨别尾调用以外，另一个原因则是堆栈信息会在优化的过程中丢失，这对于调试是不方便的，另外一些依赖于堆栈错误信息来进行用户信息收集分析的工具可能会失效。针对这个问题，实现一个影子堆栈可以解决堆栈信息缺失的问题，但这中解决方式相当于对堆栈进行了模拟，不能保证始终符合实际虚拟机堆栈的真实状态。另外，影子堆栈的性能开销也是非常大的。
基于以上原因，V8团队建议使用特殊的语法来指定尾递归优化，TC39标准委员会有一个还没有结论的提案叫做从语法上指定尾部调行为，这个提案由来自Mozilla和微软的委员提出。提案的具体内容可以看链接，主要是提出了三种手动指定尾调用优化的语法。
附手动优化语法
ReturnContinue
functionfactorial(n,acc=1){
if(n===1){
returnacc;
}
returncontinuefactorial(n-1,acc*n)
}
letfactorial=(n,acc=1)=>continue
n==1?acc
:factorial(n-1,acc*n);
//or,ifcontinueisanexpressionform:
letfactorial=(n,acc=1)=>
n==1?acc
:continuefactorial(n-1,acc*n);
Functionsigil
//#sigil,thoughit'salready'claimed'byprivatestate.
#function(){/*allcallsintailpositionaretailcalls*/}
//Notethatit'shardtodecidehowtoreadablysigilarrowfunctions.
//Thisisprobablymostreadable.
()#=>expr
//Thisisprobablymostinlinewiththenon-arrowsigil.
#()=>expr
//recsigilsimilartoasyncfunctions
recfunction(){/*likewise*/}
rec()=>expr
!-return
function(){!returnexpr}
//It'salittletrickytodoarrowfunctionsinthismethod.
//Obviously,wecannotpushthe!intotheexpression,andeven
//functionlevelsigilsareprettyugly.
//Since!alreadyhasastrongmeaning,it'shardtoreadthisas
//atailrecursivefunction,ratherthananexpression.
!()=>expr
//Wecoulddolikewedidfor#above,butitalsoreadsstrangely:
()!=>expr
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。