make tail-recursive procedure calls run faster, they are often said to perform tail-recursion optimization.
It would be more accurate to say that compilers that handle tail-recursion improperly perform
What I've been saying is inaccurate in one respect. I've been saying that foo should return its
result directly to f's caller, not to f. lf f was called tail-recursively, however, then the
caller of f doesn't need to touch the result
either. The truth is that foo should return its result directly to the last procedure in the
call chain that needed to do something useful with the result (as opposed to returning it immediately).
What I've just said is mighty vague, and it's misleading because it makes it sound as though
something special has to happen when foo returns; let me try again using the notion of a continuation.
All procedures take a hidden extra argument, the continuation. The continuation corresponds
roughly to the "control stack" or "dynamic link", but you should think of the continuation
as an abstract, active object like a procedure,
not as a concrete, passive data structure like a stack frame.
Procedures return simply by passing their result(s) to
the continuation they were passed, much as though the continuation were a procedure.
I can now give a more
precise definition of a tail-recursive call: A tail-recursive call is a procedure call in which
the calling procedure passes the called procedure a continuation equivalent to the continuation
it was passed. The difference between proper and improper implementation of tail-recursion
is this: A properly tail-recursive implementation will pass the
very same continuation; an improperly tail-recursive implementation effectively passes a copy
of the continuation.
In practice, the copy shares nearly all of its structure with the original continuation
so improperly tail-recursive
implementations are more efficient than the above paragraph makes them sound. I'll return to this in
my next article after we've seen continuations in action.
So far I may have left the impression that the main advantage of compiling tail-recursion properly is speed.
There's nothing wrong with speed, but it's not the real reason that proper handling of tail-recursion
is important. The real reason is portability. Implementations that handle tail-recursion
improperly can't run certain perfectly good programs that run fine in properly tail-recursive
implementations. That is why all implementations of Scheme are required to handle tail-recursion properly.
Before we look at why someone might want to make heavy use of tail-recursion, let's examine a
simple program whose only use is to tell whether an implementation handles tail-recursion properly.
If it works, the implementation is properly tail-recursive; if it doesn't, it isn't.
This program essentially counts down from one million before returning true. Two arguments are used
instead of one to make it less likely that the program will be slowed by bignum arithmetic.
Two procedures are used instead of one because some compilers handle self-tail-recursion,
where a procedure calls itself tail-recursively, but do not
handle general tail-recursion properly. Sometimes a compiler will handle tail-recursion
properly even though a matching interpreter will not, or vice versa.
This program will probably run for several CPU minutes if interpreted,
and for several seconds if compiled, but on slow machines it may take a minute or more
even when compiled or take nearly forever when interpreted.
Please don't run this program on a time-shared machine during the busiest
part of the day unless you want to get me in trouble.
(define (fool x y)
(if (zero? y)
(if (zero? x) #t (foo1 (— x 1) 1000))
(foo2 x (" Y 1))))
(define (foo2 x y)
(if (zero? y)
(if (zero? x) #f (foo2 (- x 1) 1000))
(foo1 x (- y 1))))
(foo1 1000 0)