2008年4月8日星期二

阶乘(factorial)&尾递归(Tail Recursion)

今天看了用递归计算阶乘咋不行呢?》受益良多,这里做下小结。

传统的递归算法写起来很漂亮,代码很简洁,但是没递归一次就需要更深一层的堆栈支持,可能会造成内存溢出而失败,所以递归和goto语句一样声名狼藉。
甚至《代码大全》的作者有这样一句话:如果为我工作的程序员用递归去计算阶乘,那么我宁愿换人。作者对递归的态度相当谨慎,这在静态命令式语言中显然是正确的,但是在函数式语言中,由于有尾递归优化的存在,递归反而是最自然的形式,况且我打心里认为递归更符合人类思维。(by )

尾递归就是从最后开始计算,每递归一次就算出相应的结果,也就是说,函数调用出现在调用者函数的尾部,因为是尾部,所以根本没有必要去保存任何局部变量,直接让被调用的函数返回时越过调用者,返回到调用者的调用者去。举例说明。
 
线性递归(传统递归方式):
function recursion(n){
    return n==1?1:n*recursion(n-1);
}

 
尾递归:
function tailRecursion(n, a){
    a = a||1; // 尾递归之尾,即上次递归结果。
    return n==1?a:tailRecursion(n-1, a*n);
}


这里将基于尾递归的求数值阶乘算法贴下:
Math.factorial_III = function(n){
    var a = arguments[1]||1;
    return n<=1?a:Math.factorial_III(n-1, a*n);
};
 
效率上和循环迭代、阶乘改进算法相当甚至稍胜出(ie6,firefox2,safari3),普通递归的效率最为底下,且需要深入堆栈。
 
参考:
尾递归》-百度百科
用递归计算阶乘咋不行呢?》-

没有评论:

发表评论