🚀 go-pugleaf

In article <20000008@uicsrd> harrison@uicsrd.CSRD.UIUC.EDU writes:
>It seems to me that if tail recursion incurs a penalty of space proportional
>to the number of calls, plus time to garbage collect the space, then it is
>significantly more expensive than iteration.

Tail recursion in Scheme doesn't incur any space penalty at all.  I can't
speak for all implementations of Scheme (because many pure interpreters do
indeed create garbage as part of the interpretation process) but I know that
if you say something like

        ((rec loop (lambda () (loop))))

in PC Scheme or MacScheme or compiled T3 you will get a tight infinite
tail-recursive loop in which no storage is allocated and the garbage
collector never runs.  (Not all infinite loops have this property, of
course; for example ((rec loop (lambda (n) (loop (1+ n)))) 0) will
eventually allocate storage for bignums.)

>                                              I have always assumed that the
>'stack' in Scheme is actually maintained as a heap; my confusion came in
>reading the claim above (and in several other presentations of Scheme) that
>tail-recursive calls occur with no net growth in the stack.  What this seems
>to mean in reality is merely that unwinding from a series of tail recursive
>calls takes constant time (if we ignore the expense of garbage collecting
>all the stack frames allocated).

No, it means that tail-recursion is as efficient as iteration in both
time and space.  That's not to say that any particular compiler will
generate exactly the same code for a do loop that it does for an equivalent
tail recursion, but if there's a significant difference in performance then
something's wrong with the compiler.

Peace, William Clinger
Tektronix Computer Research Lab