尾调用优化

定义

尾调用（Tail Call）：某个函数的最后一步是调用另一个函数。

简单的理解就是在函数体内，最后一行 return 了一个函数调用。注：仅仅只能是函数调用，任何其他的形式都不能认为是尾调用。

以下都不属于尾调用

// 情况一，并不是在 return 时调用。
function f(x){
    let y = g(x);
    return y;
}

// 情况二，调用后仍需要进行运算。
function f(x){
    return g(x) + 1;
}

// 情况三，没有 return。
function f(x){
    g(x);
}

以下属于尾调用，函数最后 return 了一个和 f 函数无关的 g 函数。

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

理解

函数调用时会传入很多的信息，这些信息都会被保存在一个调用帧中（参数，变量等信息），如果在函数 A 中调用了函数 B ，那么在函数 A 的调用帧中，会产生一个 B 的调用帧，当 B 执行结束后，将函数 B 的调用结果返回到 A 的调用帧中，这样就形成了一个函数的调用栈。

试想一下，上述情况中，假如 A 的调用帧在执行 B 的时候已经和 B 无关了（所有有关的信息通过参数传入，B 函数的调用帧保存了参数信息），并且 B 的调用是 A 中需要执行的最后一行代码，也就是说 A 调用帧中的信息在 B 执行时，并且在 B 执行结束之后都是没用的，所以针对于这种情况，我们可以直接舍弃 A 的调用帧，直接把 B 的调用帧给提到 A 的调用帧的位置，这样调用栈就少了一层。

代码解释

function f() {
    let m = 1;
    let n = 2;
    return g(m + n);
}
f();

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

// 等同于
g(3)

这就叫做 尾调用优化（ Tail call optimization ），即只保留内层函数的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是 尾调用优化 的意义。

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

在写递归时，经常会出现内存溢出的情况，由于函数调用自身，导致调用栈不断增加，当内存不足时，容易发生栈溢出的错误。

但是结合上面提出的尾调用优化，试想一下，如果函数的递归符合尾调用优化，那么是不是不会存在栈溢出的情况了，因为函数调用栈始终只有一层。

ok 来个简单的递归例子，阶乘函数：

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

factorial(5);           // 120

很明显，这个函数并没有实现尾调用优化，函数执行的最后一行包含了对当前调用帧中信息的引用，即 n 。

我们改写一下，让它符合尾调用优化

// 将阶乘的结果当做函数参数传入
function factorial(n, total) {
    if (n === 1) return total;
    return factorial(n - 1, n * total);
}

factorial(5, 1)         // 120

另外一个例子， Fibonacci 数列，未经优化：

function Fibonacci (n) {
    if ( n <= 1 ) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10)           // 89
Fibonacci(100)          // 堆栈溢出
Fibonacci(500)          // 堆栈溢出

已优化

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
    if( n <= 1 ) return ac2;
    return Fibonacci2 (n - 1, ac2, ac1 + ac2)
}

Fibonacci2(100)         // 573147844013817200000
Fibonacci2(1000)        // 7.0330367711422765e+208
Fibonacci2(10000)       // Infinity

可见尾调用的优化的关键点在于将包裹函数中数据的引用作为返回函数的参数。

当前环境下的实现

实际测试下来，目前的环境基本都没有实现尾调用优化，虽然在阮老师提到严格模式是实现的，但经过测试并没有，所有要实现尾调用优化，还要等等。

但，正式的没有，兼容的还是有的。

一个简单递归函数

function sum(x, y) {
    if (y > 0) {
        return sum(x + 1, y - 1);
    } else {
        return x;
    }
}

sum(1, 100000);
// Uncaught RangeError: Maximum call stack size exceeded(…)

很明显调用栈溢出。

实现一个蹦床函数将递归转换为循环执行。

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

但这很明显有个缺点，就是我们得修改我们原本的递归函数，因为这个蹦床函数调用传入的函数的返回值是一个函数，而不是函数调用，所以我们需要修改我们的递归函数。

function sum(x, y) {
    if (y > 0) {
        return sum.bind(null, x + 1, y - 1)
    } else {
        return x
    }
}

trampoline(sum(1, 100000))
// 100001

这个无疑会增加编写代码的难度。那么有一个完美的解决方案吗？有

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 (y > 0) {
        return sum(x + 1, y - 1);
    }
    else {
        return x;
    }
})

sum(1, 100000);
// 100001

具体的执行过程其实就是一个保存参数的过程，关键点在于 active 。