Python和Node.js支持尾递归吗？

shisgmei

　　什么是尾递归？简单来说就是最后返回的只是一个函数的调用，而不用保存多余的局部变量。
看一个简单的计算阶乘的例子(Lua代码)：



function fact(n)
    return n==0 and 1 or n * fact(n-1)
end
　　
　　改成尾递归的方式就是：



function tail_fact(n, p)
    p = p or 1
    if n==0 then
        return p
    end
    return tail_fact(n-1, n*p)
end
　　
　　关于尾递归的更详细说明请参考：
http://en.wikipedia.org/wiki/Tail_call
　　因为使用尾递归方式的时候，是不用保存局部变量的了，所以部分语言的解析器会对尾递归做优化，减少栈空间的占用。普通的递归方式则由于需要保存局部变量，栈空间则越占越多，最终导致栈溢出。
　　Lua是支持尾递归的，所以上面的尾递归的代码，是可以很好的工作的。

Python的尾递归支持
　　Python本身是不支持尾递归的(via)，并且对递归次数有限制的，当递归次数超过1000次的时候，就会抛出“RuntimeError: maximum recursion depth exceeded”异常。
有人对此为Python的尾递归写了一个优化版本，让Python突破递归调用1000次的限制：Tail Call Optimization Decorator (Python recipe) ，或者你可以看看以下两篇文章：

• 一个很Cool的Idear->Python的尾递归优化
  
• 尾递归(Tail Recursion)
  

　　以上的Python尾递归优化可以突破1000次的递归限制，但是却对于尾递归应有的优化完全没有。以下为我的测试代码：



#recursion.py
@tail_call_optimized
def fact(n):
    return 1 if n==0 else n * fact(n-1)
　　



#tail_recursion.py
@tail_call_optimized
def tail_fact(n, p=1):
    if n==0:
        return p
    return tail_fact(n-1, n*p)
　　测试环境是Python2.7.1，计算100000的阶乘。执行recursion.py的时候，内存占用约为100M，执行tail_recursion.py的时候，内存占用占到1G的时候，还是没有执行完，我只好杀掉进程。
　　不过我确实想不明白为什么Python这里写成尾递归的方式会比会比普通方式占用多那么多内存呢？

Node.js对尾递归的支持
　　我知道JavaScript是不支持尾递归的。ES4的时候曾经提过要加入尾递归的支持，不过后来被去掉了(via)。
周爱民的《Javascript语言精髓与编程实践》其中也提到：

• “然而不幸的是。目前已知的javascript 的解释环境中并不支持这种特性（尾递归）。因此，我们在这里讨论函数室式时，可以说“能够通过函数递归来消灭循环语句”，但在不支持尾递归（及其优化技术）的javascript中，这种实现将以大量栈和内存消耗为代价”
  

　　Node.js是基于Google V8的，所以在Chrome的控制台测试了一下：

　　从结果看来，基本没戏了。但是还是在node.js写了代码验证一下。



// recursion.js
function fact(n){
    if(n == 0){
        console.log('fact: ');
        console.dir(process.memoryUsage() );
    }
    return n==0 ? 1 : n * fact(n-1);
}
　　



// tail_recursion.js
function tailFact(n, p){
    p = p || 1;
    if(n==0){
        console.log('tail fact: ');
        console.dir(process.memoryUsage() );
        return p;
    }else{
        return tailFact(n-1, p*n);
    }
}
　　
　　以下为计算13000的阶乘时内存占用情况：



$ node recursion.js
fact:
{ rss: 7892992,
  vsize: 55169024,
  heapTotal: 2861216,
  heapUsed: 1634612 }
　　



$ node tail_recursion.js
tail fact:
{ rss: 7901184,
  vsize: 55169024,
  heapTotal: 2869376,
  heapUsed: 1791520 }
　　从结果来看，尾递归的方式占用的内存还要多。
　　下面再来看看计算13000的阶乘，循环1000次，然后计算平均每次的执行时间：



var start = Date.now();
for(var i=0; i