tail recursion

(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.

 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);
     }
 }

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.

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);
}
}
}
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.
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)
{
while (null != l) {
if (max_so_far < head(l)) {
max_so_far = head(l);
}
l = tail(l);
}
return max_so_far;
}

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "tail recursion", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/tailRecursion.html