Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!tut.cis.ohio-state.edu!rutgers!mit-eddie!xn.ll.mit.edu!hsdndev!husc6!carlton
From: carlton@husc10.harvard.edu (david carlton)
Newsgroups: comp.lang.scheme
Subject: Tail recursion - it's not just for breakfast any more.
Message-ID: <CARLTON.91May11224629@husc10.harvard.edu>
Date: 12 May 91 02:46:29 GMT
Sender: news@husc6.harvard.edu
Distribution: comp
Organization: Citizens for Boysenberry Jam
Lines: 75
Lyric: I'm a Zarathustra booster and it's good enough for me.

(Terminological warning: throughout this article I am going to use the
phrase "Tail-recursive procedure" to mean "procedure guaranteed to use
a finite amount of stack space", and similarly for related phrases.
Apologies if this grates on anybody's nerves.  Actually, it doesn't
mean that, either - not all scheme implementations use a stack, after
all.  But I'm at a bit of a loss as to how to describe it in an
implementation-independent manner.)

Everybody knows that writing procedures in a tail-recursive way is a
Good Thing.  I'm curious as to just how much of a good thing people
thing it is, though, and how much it is worth it to people to write a
procedure in a tail-recursive manner as opposed to in some other
manner which might have other benefits.  For example, consider the
following two definitions of "append":

(define append1
  (lambda (x y)
     (let loop ((x x))
        (if (null? x) y
            (cons (car x) (loop (cdr x)))))))

(define append2
  (lambda (x y)
     (reverse
        (let loop ((y y)
                   (acc (reverse x)))
           (if (null? y) acc
               (loop (cdr y)
                     (cons (car y) acc)))))))

The second is tail-recursive (assuming, of course, that reverse is
written in a tail-recursive manner); the first isn't.  But the second
is (on all implementations that I've tried it out on, at any rate)
slower than the first, though only by a constant factor.  (Somewhere
around 2 to 4, usually.)  And while it uses up about the same amount
of live space in the heap as the first one does, it conses more and so
will invoke the garbage collector more often.  Which one do you use?
The second one really is more likely to work, in the sense that it
will cause the implementation to run out of space much less often than
the first one does.  But it's slower, and so you lose the vast
majority of the times that you call append.

So what are your heuristics for choosing whether or not to write a
procedure in a tail-recursive manner?  Of course, if the
tail-recursive version uses up more heap space than the
non-tail-recursive version, effectively transferring memory usage from
one place to another, then you just use whichever one is faster.  And
if you are writing something like a repl loop which may never exit
then you write it in a tail-recursive manner.  But what about other
situations?  What if the tail-recursive version takes time order of
the square of the length of its input, say, while the other version
takes time order the length of its input?  What factors in the
implementation of your Scheme system could cause you to choose one
method or another?  Etc...

To be sure, the example I gave isn't the best.  (Though it is the best
that I know of, and one that actually has come up in my programming;
but I haven't looked very hard, and would really prefer a better
example.  Anybody?)  The careful reader has noticed by now that the
procedures aren't in fact equivalent, and in particular the
tail-recursive version isn't quite the append in the standard
(ignoring, of course, the fact that they should be taking a variable
number of arguments, anyways.)  Once you fix that and do some more
simple speedups (involving replacing some calls to reverse by calls to
reverse! or other slightly modified versions of reverse), you find
that you can actually make the tail-recursive version about as fast
and about as space-efficient as the non-tail-recursive version.  Is
this in fact an inherent property of tail-recursion?  (Seems unlikely
to me, but I don't have any real evidence one way or another.)  Can
one in fact come up with a procedure whose fastest tail-recursive
implementation has slower order than its fastest implementation?  What
about memory usage?

david carlton
carlton@husc10.harvard.edu