Tail recursion

related topics
{math, number, function}
{system, computer, user}
{style, bgcolor, rowspan}

In computer science, a tail call is a subroutine call producing a return value which is then returned by the calling procedure. In other words, it is a subroutine call which is immediately followed by a return from the calling subroutine, which must return the obtained value. The call site is then said to be in tail position. If a subroutine performs a tail call to itself, it is called tail recursive. This is a special case of recursion.

Tail calls are significant because they can be implemented without consuming space on the call stack, because the call can replace the stack frame of the current procedure with the one of the newly called procedure. To do so, it suffices to adjust the subroutine arguments and then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination (TCE).

Traditionally, tail call elimination is optional, and it can also be called tail call optimization (TCO). However, in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops. In such cases, it is not correct to refer to it as an optimization, even if it is customary practice.

Contents

Description

When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack alone (except maybe for function arguments), and the newly called function will return its result directly to the original caller. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed.

For non-recursive function calls, this is usually a micro-optimization that saves little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be huge, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack space requirements from linear, or O(n), to constant, or O(1). Tail call elimination is thus required by the standard definitions of some programming languages, such as Scheme,[1][2] languages in the ML family, and Haskell. In the case of Scheme, the language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context.[3] Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail call elimination, can also be called 'properly tail-recursive'.[1]

Full article ▸

related documents
Kernel (matrix)
Cantor's diagonal argument
Integer
Equivalence relation
Square root
Icon (programming language)
Cholesky decomposition
Standard ML
Template (programming)
Supremum
Hausdorff dimension
Extended Euclidean algorithm
Complete metric space
Taylor's theorem
L'Hôpital's rule
Insertion sort
PL/SQL
Dirac delta function
Metric space
Vigenère cipher
Set (mathematics)
Operator
Natural number
Interpolation
Exponential function
Monoid
Abstraction (computer science)
Analysis of algorithms
MATLAB
Semidirect product