## tail call optimisation

### Nearby terms:

tag name ♦ **tail call optimisation** ♦ tail call optimization ♦ tail circuit

Try this search on Wikipedia, OneLook, Google

## tail call optimization

### Nearby terms:

tail call optimisation ♦ **tail call optimization** ♦ tail circuit ♦ tail recursion

Try this search on Wikipedia, OneLook, Google

## tail circuit

A circuit which connects the serial lines of two modems together.

[Why do that?]

Last updated: 1996-10-16

### Nearby terms:

tail call optimization ♦ **tail circuit** ♦ tail recursion ♦ tail recursion modulo cons

Try this search on Wikipedia, OneLook, Google

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

Last updated: 2006-04-16

### Nearby terms:

tail circuit ♦ **tail recursion** ♦ tail recursion modulo cons ♦ tail recursion optimisation

Try this search on Wikipedia, OneLook, Google

## tail recursion modulo cons

A generalisation of tail recursion introduced by D.H.D. Warren. It applies when the last thing a function does is to apply a constructor functions (e.g. cons) to an application of a non-primitive function. This is transformed into a tail call to the function which is also passed a pointer to where its result should be written. E.g.

f [] = [] f (x:xs) = 1 : f xsis transformed into (pseudo C/Haskell):

f [] = [] f l = f' l allocate_cons f' [] p = { *p = nil; return *p } f' (x:xs) p = { cell = allocate_cons; *p = cell; cell.head = 1; return f' xs &cell.tail }where allocate_cons returns the address of a new cons cell, *p is the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University of Edinburgh 1980].

Last updated: 1995-03-06

### Nearby terms:

tail recursion ♦ **tail recursion modulo cons** ♦ tail recursion optimisation

Try this search on Wikipedia, OneLook, Google

## tail recursion optimisation

(TRO) Discarding the calling environment (call stack frame) when the last thing a function or procedure does is to call itself. This is important when a procedure calls itself recursively many times since, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the last call terminated.

Tail recursion optimisation is a special case of last call optimisation but it allows the further optimisation that some arguments may be passed in situ, possibly in registers. It allows recursive functions to be compiled into iterative loops.

See also conversion to iteration, tail recursion modulo cons.

Last updated: 2006-04-16

### Nearby terms:

tail recursion modulo cons ♦ **tail recursion optimisation** ♦ tail-strict

Try this search on Wikipedia, OneLook, Google

## tail-strict

A tail-strict function evaluates every cons cell in its (list) argument. It will therefore fail to terminate if its argument is an infinite list or if any tail of its argument fails to terminate. The archetypal tail-strict function is length. See also Head-strict, Hyper-strict.

### Nearby terms:

tail recursion modulo cons ♦ tail recursion optimisation ♦ **tail-strict** ♦ TAL ♦ TALE

Try this search on Wikipedia, OneLook, Google

Tweet