Tail recursion: Meaning (information, definition, explanation, facts)

Tail recursion is a special case of recursion that can be transformed into an iteration. It is used in functional programming languages where the declarative approach and explicit handling of state emphasize recursive functions that rapidly fill the stack. Replacing recursion with iteration saves stack space and improves efficiency.

The transformation is possible when the recursive calls are the last statements in the function (hence tail recursion). In simple terms, there is nothing more to do after the recursive call returns, so the call is replaced by a goto. This introduction of jumps is called tail call optimization, and is not restricted to recursive calls.

Several functions may be mutually recursive. If the entire loop is constructed with tail recursion then tail call optimization will give a properly tail recursive implementation that does not consume stack space; this is a requirement in, for example, the standard definition of Scheme.

The tail expression in Scheme is defined as follows:

1. The body of a lambda expression is a tail expression.

2. If (if E₀ E₁ E₂) is a tail expression, then both E₁ and E₂ are tail expressions.

3. Nothing else is a tail expression.

Take this Scheme program as an example (adapted from the Lisp programming language page to a more SICPish style):

(define (factorial n) (define (iterate n acc) (if ( are tail expressions.

3. Nothing else is a tail expression.

Take this Scheme program as an example (adapted from the Lisp programming language page to a more SICPish style):

(define (factorial n) (define (iterate n acc) (if (iterate calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:

call factorial (3) call iterate (3 1) call iterate (2 3) call iterate (1 6) return 6 return 6 return 6 return 6

into the more space- (and time-) efficient variant:

call factorial (3) replace arguments with (3 1), jump into "iterate" replace arguments with (2 3), re-iterate replace arguments with (1 6), re-iterate return 6

This reorganization saves space because no state except for the calling function's address needs to be saved, neither on the stack nor on the heap. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions.

Some programmers working in functional languages will rewrite recursive code to be tail recursive so they can take advantage of this feature. This often requires addition of an "accumulator" (acc in the above implementation of factorial) as an argument to a function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.

Since having a complete call graph is a daunting task for compilers, a mere tail call is usually referred to as being tail recursive.

Besides space and execution efficiency, the tail recursion is important to allowing a common idiom in functional programming, continuation passing style (CPS) without quickly running out of stack space.

Tail recursion modulo cons

Tail recursion modulo cons is a generalisation of tail recursion introduced by D. H. D. Warren. Sometimes the result of a recursive call is not meant to be returned on the call stack, but rather written into data structure in memory. This can be made tail-recursive by providing the recursive call with the address where it should place its result. For example, consider a function that accepts a list and returns a list of ones with the same length, described here in C:

list *f(list *input)
{
  list *head;

  if(input == NULL) {
    head = NULL;
  } else {
    head = malloc(sizeof(list));
    head->value = 1;
    head->next = f(input->next);
  }
  return head;
}

In this form the function is not tail-recursive, because control returns to the caller after the recursive call to set the value of head->next. Applying tail recursion modulo cons gives the following tail-recursive implementation:

list *f(list *input)
{
  list *head;

  fprime(input, &head);
  return head;
}

void fprime(list *input, list **p)
{
  if(input == NULL) {
    *p = NULL;
  } else {
    *p = malloc(sizeof(list));
    (*p)->value = 1;
    fprime(input->next, &(*p)->next);
  }
}

This implementation can be converted to iterative form.

list *f(list *input)
{
  list *head;
  list **p;

  p = &head;
  while(input != NULL) {
    *p = malloc(sizeof(list));
    (*p)->value = 1;
    input = input->next;
    p = &(*p)->next;
  }
  *p = NULL;
  return head;
}

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

This article was originally based on material from the Free On-line Dictionary of Computing and is used with under the GFDL.