tail recursion

(redirected from Tail-recursive)

tail recursion

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 ?
1986; Kranz 1987] compiler generates very fast code by having six different closure allocation strategies for different kinds of functions; the MIT scheme compiler [Rozas 1984; Hanson 1990] implements tail-recursive procedure calls as efficiently as most explicit iteration constructs by using special closure representations and calling conventions; the Standard ML of New Jersey compiler (SML/NJ) [Appel and Macqueen 1991; Appel and Shao 1992] represents the return-continuation closure using a set of callee-save registers to achieve closure sharing and fast access to free variable bindings.
Efficient stack allocation for tail-recursive languages.
But those too are complied as syntactic sugar for tail-recursive procedures, demonstrating that iteration is just a special case of recursion and that GOTO and break are unnecessary special cases of procedure invocation!