tail recursion


Also found in: Wikipedia.

tail recursion

(programming)
When the last thing a function (or procedure) does is to call itself. Such a function is called tail recursive. A function may make several recursive calls but a call is only tail-recursive if the caller returns immediately after it. E.g.

f n = if n < 2 then 1 else f (f (n-2) + 1)

In this example both calls to f are recursive but only the outer one is tail recursive.

Tail recursion is a useful property because it enables tail recursion optimisation.

If you aren't sick of them already, see recursion and tail recursion.
References in periodicals archive ?
In a real compiler, the stack-based scheme must also incorporate a wide range of other extensions to support tail recursion [Hanson 1990], generational stack collection [Cheng et al.
Without the stack, supporting tail recursion, generational garbage collection, efficient call/cc, and exception handling all becomes straightforward [Appel 1992].
This is achieved without treating tail recursion as a special case (as was done by Kranz [1987]).
In our heap-based scheme, the correctness is straightforward because dead frames are automatically reclaimed by the garbage collector; the efficiency is achieved by using the loop-header technique [Appel 1994] to hoist the loop-invariant free variables out of the tail recursion, and using the callee-save registers [Appel and Shao 1992] to simulate the top reusable stack frames.
Recently, Clinger [1998] gave a formal and implementation-independent definition of the proper tail recursion and the SSC rule.
For example, in Kranz's Orbit compiler [Kranz 1987], all tail recursions are assigned a so-called stack/loop strategy, and all general recursions are assigned a stack/recursion strategy.