Tail Recursion
Recursion is a software routine calling itself. Tail recursion is where the call is the last statement routine. The classic example of a recursive function is the factorial 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 factorial 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.
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 this example) to complete the transformation. In the parser, the accumulator t was already present.
The factorial is an easy example of recursion, but it doesn'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.
—T.S.
