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

2011/7/31 13:33:53ChineseComment(0)Browse(3182)

什么是尾递归？简单来说就是最后返回的只是一个函数的调用，而不用保存多余的局部变量。
看一个简单的计算阶乘的例子(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) ，或者你可以看看以下两篇文章：

以上的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<1000; i++){
    tailFact(13000);
}
console.log( (Date.now() - start)/1000 );

以下为执行结果：

$ node recursion.js 
0.257

$ node tail_recursion.js 
0.277

阿门，无论是内存占用还是执行效率，尾递归的方式都要比普通方式差。

看来V8是对于尾递归的方式完全没有做优化了，对于Node.js异步调用到处是的情况下，没有对尾调用做优化的话，栈空间浪费很严重啊！不知道我这样认为对不对？忘记一点是“异步”的，异步回调栈是清空的了，不存在该问题。