关于尾递归

初稿于20060522
关于尾递归
Tail Recursion

(递归在数学中是完美的，在程序中也能体现这种优雅。尤其是在函数式编程中)
Recursion is a software routine calling itsetf. Tail recursion is where the call is the last statement routine.The clasic example of a recursive function is thefactorial function:
long fact(long n){
if(n<2) return 1;
return n*fact(n-1);
}

which is tail recursive because the call to itself,fact(n-1),is the last line of the function.In practice,recursion is a terrible way to calculate the fractorial because it uses so much stack space and adds function call overhead.in modern systems,the function call overhead may not be that high,unless you are doing a huge number of calculations.but stack overflow can be a problem(递归增加栈的开销,如果数字太大的话,也有可能引发溢出)

it is common for lisp compilers to detect tail recursion and replace the call statement with a goto.some other compilers-the gnu c compiler is one example-can also make this replacement.(一般地,递归均可以用goto语句来替换)
when performing tail recursion manually,you usually replace the recursion with a loop:
long fact(long n){
long result=1;
while(n>1){
result=n*result;
--n;
}
}
as you can see,you sometimes have to add an accumulator(result,in the example) to complete the transformation.in the parser,the accumulator t was already present.
the factorial is an easy example of recursion,but is does't really illustrate the power of the technique,recursive-descent parsing is a much better example,using recursion keeps the logical flow of the program much cleaner and easier to debug.