什么是尾递归？简单来说就是最后返回的只是一个函数的调用，而不用保存多余的局部变量。

看一个简单的计算阶乘的例子(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

　　

关于尾递归的更详细说明请参考：

因为使用尾递归方式的时候，是不用保存局部变量的了，所以部分语言的解析器会对尾递归做优化，减少栈空间的占用。普通的递归方式则由于需要保存局部变量，栈空间则越占越多，最终导致栈溢出。

Lua是支持尾递归的，所以上面的尾递归的代码，是可以很好的工作的。

Python的尾递归支持

Python本身是不支持尾递归的()，并且对递归次数有限制的，当递归次数超过1000次的时候，就会抛出“RuntimeError: maximum recursion depth exceeded”异常。

有人对此为Python的尾递归写了一个优化版本，让Python突破递归调用1000次的限制： ，或者你可以看看以下两篇文章：

以上的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的时候曾经提过要加入尾递归的支持，不过后来被去掉了()。

周爱民的《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异步调用到处是的情况下，没有对尾调用做优化的话，栈空间浪费很严重啊！不知道我这样认为对不对？忘记一点是“异步”的，异步回调栈是清空的了，不存在该问题。

Enjoy!