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

function fact(n, acc){
    if(n==0)return acc;
    return fact(n-1, acc*n)
}

function fact(n){
    var acc=1,i=n
    while(i!=0){
        acc=acc*i;
        i-=1;
    }
    return acc
}

在clojure里, 尾递归是用 recur 来保证(scalar貌似是@tail annotation), 好处是

1. 用recur的一定是尾递归, 直接优化
2. 编译器可以检查recur出现的位置是否为tail

举个最简单的例子, 相互递归经常用于状态机的实现, 比如自动贩卖机, 假设这台贩卖机非常简单, 只吃五块,只卖巧克力

那么输入集是 [五块, 选巧克力, 找零], 所以贩卖机正常的process是类似

5块 -> 巧克力 -> 找2块

好吧, 我们来实现一把

function eat_money(input_seq){
    var input = input_seq.shift()
    if(input== '五块')
        console.log('收到呢,选个巧克力吧^_^')
        choose(input_seq)
    else
        eat_money(input_seq)
}

function choose(input_seq){
    var input = input_seq.shift()
    if(input== '巧克力')
        console.log('选了巧克力, 按下找零按钮, 我还欠你两块钱哦')
        changes(input_seq)
    else
        choose(input_seq)
}

function changes(input_seq){
    var input = input_seq.shift()
    if(input=='找零')
        console.log('欢迎再次光临')
        eat_money(input_seq)
    else
        changes(input_seq)
}

假设我是个怪蜀黍QA,来到这个贩卖机上怒点这样以系列操作, 看我们的贩卖机有没有疯掉

['巧克力', '巧克力', '找钱', '五块', '找钱', '五块', '巧克力', '五块', '找钱']

现在问题来了, 如果我的 input_seq 非常长, 比如

for(var n=15;n>0;n--){
  input_seq=input_seq.concat(input_seq)
}
input_seq.length // => 294912

现在 input_seq 非常大, 再试试(请到node上试)

...
收到呢,选个巧克力吧^_^
RangeError: Maximum call stack size exceeded
...

Trampoline就是用来解决相互递归爆栈的问题, 等等, 什么是Trampoline

trampoline是一个函数:

1. 接受一个函数, 一个或多个函数的参数
2. 调用该函数
3. 如果返回值是个函数, 继续调用
4. 如果返回值不是函数, 停止

比如可以把贩卖机简单的改造一下, 让他返回函数, 而不是直接调用其他函数, 注意第6行

 1: function eat_money(input_seq){
 2:   if(input_seq.length==0)return
 3:   var input = input_seq.shift()
 4:   if(input== '五块'){
 5:     console.log('收到呢,选个巧克力吧^_^')
 6:     return function(){
 7:       return choose(input_seq)
 8:     }
 9:   }else{
10:     return function(){
11:       return eat_money(input_seq)
12:     }
13:   } 
14: }

这样每次调用eat_money其实返回一个闭包, 需要再调用一下才能真的执行 choose 函数.

经过这样的改造以后(当然其他函数也要类似的加闭包), 就可以用 trampoline 来执行他们了

mori.trampoline(eat_money,input_seq)

由于eat_money返回一个闭包,也就是函数, trampoline会继续执行这个返回的闭包,直到返回的不是函数为止

而trampoline优化之前的 eat_money, 其实就是把最后调用的函数压到调用栈里, 然后 压入调用栈的这个函数比如是 choose 又调用另一个函数比如 changes, 然后一直压压压, 压到最后再从栈里弹出来一个一个执行.

function eat_money(input_seq){
    return choose(input_seq){
        return changes(input_seq){
            return ...
        }
    }
}

所以如果压入的函数个数超过栈的容量, 栈 菊花 就被爆了 而trampoline则是在函数最后返回一个闭包, 闭包内的递归调用并未被调用, 也就是未被压栈, 所以是这样的

var res = eat_money(input_seq)
while(true){
    if(typeof res =='function')res = res()
    else
        break
}

优化成循环了不是.

完整代码, 如果uncomment 注释掉的代码浏览器会timeout, 请在node上跑, 反正不会爆栈