|
#REDIRECT [[Tail call]]
{{merge|Tail call|discuss=Talk:Tail recursion#Should be merged with Tail call|date=July 2010}}
In [[computer science]], '''tail recursion''' (or '''tail-end recursion''') is a special case of [[Recursion_(computer_science)|recursion]] in which all recursive calls are [[tail call]]s.
Such recursions can easily be transformed to iterations. Replacing recursion with [[iteration]], manually or automatically, can drastically decrease the amount of [[Call stack|stack]] space used and improve efficiency. This technique of iterative calculation is commonly used with [[functional programming]] languages, where the [[declarative programming|declarative approach]] and explicit handling of [[state (computer science)|state]] promote the use of recursive functions that would otherwise rapidly fill the [[call stack]].
{{Redirect category shell|1=
==Examples==
{{r from merge}}
}}
Take this [[Scheme (programming language)|Scheme]] program as an example:
<source lang="scheme">
;; 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)))))
</source>
This program is not written in a tail recursion style. Now take this [[Scheme (programming language)|Scheme]] program as an example:
<source lang="scheme">
;; 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)))))
</source>
The inner procedure <code>fact</code> calls itself ''last'' in the control flow. This allows an [[interpreter (computer software)|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 [[Algorithmic efficiency|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 (<code>acc</code> 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.{{Fact|date=April 2007}}<!-- an example would be good here -->
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 (jargon)|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 (programming language)|C]]:
<source lang="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;
}
}
</source>
In this form the function is not tail-recursive, because control returns to the caller after the recursive call to set the value of <code>head->next</code>. 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:
<source lang="c">
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);
}
}
</source>
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:
<source lang="c">
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;
}
</source>
==See also==
*[[Course-of-values recursion]]
*[[Recursion (computer science)]]
==References==
{{wiktionarypar|tail recursion}}
* D. H. D. Warren, ''DAI Research Report 141'', University of Edinburgh, 1980.
<references/>
{{FOLDOC}}
[[Category:Theory of computation]]
[[Category:Articles with example C code]]
[[Category:Articles with example Scheme code]]
[[Category:Control flow]]
[[Category:Scheme (programming language)]]
| 