Tail recursion

In computer science, 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 drastically decreases the amount of stack space used and improves efficiency.

When a function is called, the computer must "remember" the place it was called from, called 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 stack, a simple list of return locations in order of the time 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. But in this case, there is no need to remember the place we are calling from — instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller. Converting a call to a branch or jump in such a case is called a tail call optimization. Note that the tail call doesn't have to literally appear after all other statements in the source code; it is only important that its result is immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed.

For normal, 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, however, the stack space and the number of returns saved can grow to huge numbers, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack requirements from linear, or O(n) stack space, to constant, or O(1) stack space.

If several functions are mutually recursive, meaning they each call one another, and each call they make to one another in an execution sequence uses a tail call, 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 notion of tail position in Scheme can be defined as follows:

1. The body of a lambda expression is in tail position.
2. If (if E₀ E₁ E₂) is in tail position, then both E₁ and E₂ are in tail position.

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 (<= n 1)
          acc
          (iterate (- n 1) (* acc n))))
    (iterate n 1))

As you can see, the inner procedure 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 generalization of tail recursion introduced by David H. D. Warren. As the name suggests, the only operation needed after the recursive call is a cons, which adds a new element to the front of the list that was returned. The optimization moves this operation inside the recursive call by creating a list node with the front element, and passing a reference to this node as an argument.

For example, consider a function that accepts a linked 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->next = f(input->next);
    head->value = 1;
  }

  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. But on resumption, the caller merely prepends a value to the result from the callee. So the function is tail-recursive, save for a "cons" action, that is, tail recursive modulo cons. Warren's method gives the following purely 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);
  }
}

Note how the callee now appends to the end of the list, rather than have the caller prepend to the beginning.

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;
}

References

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

de:Endrekursion

ja:末尾再帰