Tail recursion
 |
In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which all recursive calls are tail calls. Such recursions can easily be transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique of iterative calculation is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack.
Examples
Take this Scheme program as an example:
;; factorial : number -> number
;; to calculate the product of all non-negative integers
;; less than or equal to n.
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
This program is not written in a tail recursion style. Now take this Scheme program as an example:
;; factorial : number -> number
;; to calculate the product of all non-negative integers
;; less than or equal to n.
(define (factorial n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i)))))
The inner procedure fact 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 fact (3 1)
call fact (2 3)
call fact (1 6)
call fact (0 6)
return 6
return 6
return 6
return 6
return 6
into the more efficient variant, in terms of space:
call factorial (3) replace arguments with (3 1), jump to "fact" replace arguments with (2 3), jump to "fact" replace arguments with (1 6), jump to "fact" replace arguments with (0 6), jump to "fact" return 6
This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. It is also worth noting, in typical implementations, the tail recursive variant will be substantially faster than the other variant, but only by a constant factor, albeit a large one.
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" argument (acc in the above example) to the 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.[citation needed]
Besides space and execution efficiency, tail recursion optimization is important in the functional programming idiom known as continuation passing style (CPS), which would otherwise quickly run 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 duplicates a linked list, described here in C:
list *duplicate(list *input)
{
if (input == NULL) {
return NULL;
} else {
list *head = malloc(sizeof *head);
head->value = input->value;
head->next = duplicate(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. 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 *duplicate(const list *input)
{
list *head;
duplicate_prime(input, &head);
return head;
}
void duplicate_prime(const list *input, list **p)
{
if (input == NULL) {
*p = NULL;
} else {
*p = malloc(sizeof **p);
(*p)->value = input->value;
duplicate_prime(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.
The properly tail-recursive implementation can be converted to iterative form:
list *duplicate(const list *input)
{
list *head;
list **p = &head;
while (input != NULL) {
*p = malloc(sizeof **p);
(*p)->value = input->value;
input = input->next;
p = &(*p)->next;
}
*p = NULL;
return head;
}
See also
References
- D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.