尾调用优化(Tail Call Optimization)

1.什么是尾调用

  尾调用(Tail Call)是函数式编程的一个重要概念，用简单的一句话描述就是“在函数的最后一步调用函数”

function f(x){
    let y=x+1;
    return g(y);
}

上面代码中，函数f的最后一步是调用函数g，这就是尾调用。
以下几种情况，都不属于尾调用：

//情况一
function f(x){
    let y=g(x);
    return y;
}
//情况二
function f(x){
    return g(x)+1;
}
//情况三
function f(x){
    g(x);
}
//情况四，尾调用函数如果是闭包函数，也不能使用尾调用优化
function f(x){
     const g=()=>x;
     return g();
}

2.尾调用优化

  正常情况下，函数调用会在内存中形成一个“调用记录”，又称“调用帧”(call frame)，保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用记录上方，还会形成一个B的调用记录，等到B运行结束，将结果返回A，B的调用记录才会消失。如果函数B内部还调用函数C，那在B的调用记录上方还有一个C的调用记录栈，以此类推，所有的调用记录，就形成一个“调用栈”（call stack）。这有可能会出现函数调用栈过大甚至溢出的情况。
  尾调用由于是函数的最后一步，所以不再需要保存外层函数的调用记录，因为调用位置，内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

function f(){
    let a=1,b=2;
    return g(a+b);
}
f();

//等价于
function f(){
    return g(3);
}

//等价于
g(3);

上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量a和b的值、函数f的调用位置等信息。但由于调用g后，函数f就结束了，所以执行到最后一步，完全可以删除函数f的调用记录，只保留g(3)的调用记录。
  这就叫做“尾调用优化”(Tail call optimization)，即只保留内层函数的调用记录，如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存，这就是“尾调用优化”的意义。

3.尾递归

  函数调用自身，称为递归。如果尾调用自身，则称为尾递归。递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易出现“栈溢出”的错误（stackoverflow）。但对于尾递归而言，由于只存在一个调用记录，所以不会发生“栈溢出”的错误。

function factorial(n){
    if(n===1){
        return 1;
    }
    return n*factorial(n-1);
}
factorial(5)  //120

上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，空间复杂度O(n)，当n足够大时，则会发生调用栈溢出。如果改写成尾递归，则只保留一个调用记录，空间复杂度O(1).

function factorial(n,total){
    if(n===1){ return total; }
    return factorial(n-1,n*total);
}
factorial(5,1)

如图

由此可见，“尾调用优化”对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。在ES6中，严格模式下，宣称支持尾调用优化这个新特性。
  但目前V8引擎并没有优化尾递归，V8团队认为做尾递归优化存在一系列问题，因此倾向于支持用显示的语法来实现，而非做优化。我自己在node环境和浏览器环境都做了测试，当尾递归函数中传入n过大时，同样会出现栈溢出的情况，不管是否开启严格模式，所以似乎尾递归优化并没有起作用。这里纯当学习一下。

4.递归函数的改写

  尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数factorial需要用到一个中间变量total，那就把这个中间变量改写成函数的参数。这样做的缺点是使函数看起来不太直观，第一眼很难看出来，为什么计算5的阶乘，需要传入两个参数5和1。两个方法可以解决这个问题。

方法一：在尾递归函数之外，再提供一个正常形式的函数

function tailFactorial(n,total){
    if(n===1) { return total; }
    return tailFactorial(n-1,n*total);
}
function factorial(n){
    return tailFactorial(n,1);
}
factorial(5);  //120

上面代码通过一个正常形式的阶乘函数factorial,调用尾递归函数tailFactorial，看起来就正常多了。
  函数式编程中有一个概念，叫做柯里化(currying)，简单来说就是将多参数的函数转换为单参数函数的形式，这里也可以使用柯里化。

function currying(fn,n){
    return function (m){
        return fn.call(this,m,n);
    }
}
function tailFactorial(n,total){
    if(n===1){ return total ;}
    return tailFactorial(n-1,n*total);
}
const factorial = currying(tailFactorial,1)
factorial(5) //120

上面代码通过柯里化，将尾递归函数tailFactorial变为只接受一个参数的factorial函数。

方法二：使用ES6的默认值特性。

function factorial(n,total=1){
    if(n===1){ return total; }
    return factorial(n-1,n*total);
}
factorial(5);

上面代码中，参数total有默认值1，调用时可以不提供这个值。

总结，递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作的命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要。对于其他支持“尾调用优化”的语言，我们需要知道循环可以用递归来代替，而一旦使用递归，就最好使用尾递归。