在ES6的严格模式下，支持尾递归的优化（目前只有Safari支持），那么在非严格模式下，我们如何自己实现尾递归的优化？

尾递归优化的原理

尾递归之所以需要优化，原因是调用栈太多，造成溢出，那么只要减少调用栈，就不会溢出。怎么做可以减少调用栈呢？就是采用“循环”换掉“递归”。

未优化代码案例

1
2
3
4
5
6
7
8
9
function sum(x, y) {
    if (y > 0) {
        return sum(x + 1, y - 1);
    } else {
        return x;
    }
}

sum(1, 100000)

上面代码中，sum是递归函数，递归次数100000，将会提示超出调用栈的最大次数

蹦床函数（trampoline）

蹦床函数可以将递归执行转为循环执行。

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

上面就是一个蹦床函数的实现，只要f执行后返回一个函数，就继续执行。
注意：这里返回一个函数，然后执行该函数，而不是函数里面调用函数，这就避免了递归执行。

然后，要将原来的递归函数改写成每一步返回另一个函数。

1
2
3
4
5
6
7
8
function sum(x, y) {
    if (y > 0) {
        // bind()为了返回函数的另一个版本。
        return sum.bind(null, x + 1, y - 1);
    } else {
        return x;
    }
}

现在，使用蹦床函数执行sum，就不会发生调用栈溢出。

1
trampoline(sum(1, 100000))

真正的尾递归优化实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function tco(f) {
    var value;
    var active = false;
    var accumulated = [];
    
    return function accumulator() {
        accumulated.push(arguments);
        if (!active) {
            active = true;
            while (accumulated.length) {
                // 这里会一直循环调用f()
                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);

上面代码中，tco函数时尾递归优化的实现。
f.apply(this, accumulated.shift()) 会一直循环调用 accumulator()，直到有value返回。
后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。