(algorithmic technique)
Definition: A special form of recursion where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame.
See also collective recursion, iteration.
Note:
Although it may not save a lot of run time, it can save a lot of memory. The following finds the maximum value in a list. The return value of the current invocation is just the return value of the recursive call. A compiler could optimize it something like the following so it doesn't allocate new space for l and max_so_far on each invocation or tear down the stack on the returns. Of course, if a compiler is good enough to find and rewrite tail recursion, it will also collapse the loop test, eliminate the assignment of max_so_far to itself, and hoist the assignment of l after the test giving the following: int max_list(list l, int max_so_far)
{
if (null == l) {
return max_so_far;
}
if (max_so_far < head(l)) {
return max_list(tail(l), head(l));
} else {
return max_list(tail(l), max_so_far);
}
}
Now there is no need to allocate new memory for the parameters or get rid of it during the returns, so this will run faster. This code transformation is simple enough to do by hand in this example, but it is much harder for complex recursive data structures, such as trees.
int max_list(list l, int max_so_far)
{
for (;;) {
if (null == l) {
return max_so_far;
}
if (max_so_far < head(l)) {
max_so_far = head(l);
l = tail(l);
} else {
max_so_far = max_so_far;
l = tail(l);
}
}
}
int max_list(list l, int max_so_far)
{
while (null != l) {
if (max_so_far < head(l)) {
max_so_far = head(l);
}
l = tail(l);
}
return max_so_far;
}
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Thu Aug 14 12:18:08 2008.
Cite this as:
Paul E. Black, "tail recursion", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/tailrecursn.html