next up previous
Next: 6 Analyzing Algorithms Up: 5 Iteration Previous: 5.2 J Example

5.3 Tail Recursion

A recursive definition, f, is said to be tail recursive if the continuation of each recursive call to f is the identity function. As long as the definition is not mutually recursive, it is an easy exercise for students to examine the source code of a definition and explicitly write the continuations to determine whether or not the definition is tail recursive. As many compilers and interpreters automatically recognize tail recursion and optimize these definitions as loops (gcc, for example), students quickly learn that they can write efficient iteration loops in a functional style.

The analysis of mutually recursive definitions is done in a similar fashion by hand, but is problematic for compilers and interpreters, particularly if the definitions are compiled separately.


next up previous
Next: 6 Analyzing Algorithms Up: 5 Iteration Previous: 5.2 J Example
2002-11-26