Seateng Blog

在Erlang中的两种递归写法
普通递归:
recursive_sum([H|T]) -> H+recursive_sum(T);
recursive_sum([]) -> 0.
尾递归:
sum(L) -> sum(L, 0).
sum([H|T], Sum) -> sum(T, Sum + H);
sum([], Sum) -> Sum.
在Erlang文档效能向导部分有说明，尾递归比普通递归更快。
普通递归H+recursive_sum(T);在recursive_sum(T);返回之前H都会被压入stack等到返回结果再计算。
递归越深，内存将被吃的越多。面向过程编程或者面向对象编程也会常用到递归函数。当在Erlang这种函数式编程里无疑将更经常使用递归函数。所以更应该注意递归函数的效率和系统开销。
反过来在面向过程或者面向对象的语言中也可以用尾递归来提高效率减少系统开销。

以PHP为例子

<?php
$n   = 3;
$sum = 0;
//尾递归
function TailRecursive($n, $sum)
{
    if ($n>0) {
        $sum += $n;
    	TailRecursive($n-1, &$sum);
    }
}
TailRecursive($n, &$sum);
echo $sum;
//普通递归
function Recursive($n)
{
    if ($n>0) {
    	return $n+Recursive($n-1);
    }else{
        return 0;
    }
}
$sum = Recursive($n);
echo $sum;
?>

当然现在很多语言的编译器都很智能会自动优化，但还是自己知根知底的好。
注：Erlang 文档关于Tail-recursive的说明