Tail-recursive Functions
Tail-recursive functions are functions in which all recursive calls are tail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a compiler or interpreter that treats tail-recursive calls as jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
| Tail recursion: | Augmenting recursion: |
|---|---|
| //INPUT: Integers x, y such that x >= y and y > 0 int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } | //INPUT: n is an Integer such that n >= 0 int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); } |
The significance of tail recursion is that when making a tail-recursive call, the caller's return position need not be saved on the call stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, on compilers that support tail-recursion optimization, tail recursion saves both space and time.
Read more about this topic: Recursion (computer Science)
Famous quotes containing the word functions:
“Adolescents, for all their self-involvement, are emerging from the self-centeredness of childhood. Their perception of other people has more depth. They are better equipped at appreciating others’ reasons for action, or the basis of others’ emotions. But this maturity functions in a piecemeal fashion. They show more understanding of their friends, but not of their teachers.”
—Terri Apter (20th century)