The merits of being properly tail-recursive
Scheme takes the stance that recursion is sufficient to express, well,
recursion, as well as the common iterative control structures, such as
loops. However, the main difference between recursion and iteration
in most other languages is that a procedure call (specifically a
recursive procedure call) consumes space, on the stack or elsewhere,
to store its context. This means that, each iteration of a loop
consumes space, and may therefore lead to stack overflow or something
similar.
However, when you formulate loops via recursion, the context does
not change between successive iterations, because the recursive
calls are "tail calls"---they have no context. Scheme guarantees
that such calls will not consume space, and it's therefore safe to
write loops this way. The tail calls compile to goto
+ parameter passing. Tail calls are important in other contexts,
because not having them can lead to space leaks.
Now, a lot code obviosuly depends on Scheme implementations having
this property because loops are so common. It's not possible to
support the general property of being properly tail-recursive after
the fact, unless you want to rewrite your whole program in terms of
goto.
Michael Sperber [Mr. Preprocessor]
Last modified: Tue Jul 14 16:04:17 MST 1998