Subject: Re: Tail recursion: Is it just a fancy name for iteration?
From: (Rob Warnock)
Date: 1998/10/25
Newsgroups: comp.lang.lisp
Message-ID: <70veca$>
Barry Margolin  <> wrote:
| >You can't effectively use continuation-passing style without
| >having tail recursion.
| Aye, there's the rub.  I don't think most humans programmers use CPS
| directly.

Not in the bulk of one's coding, no, but occasionally I find myself
quite naturally writing CPS code when I'm coding some sort of finite-state
machine (e.g., a lexical analyzer, a communications protocol, etc.).

When you consider that a tail call is really a "goto, with arguments",
a number of opportunities arise to employ it usefully. That is, the
fact that you can pass arguments with the goto partially negates the
disadvantage of the spaghetti-coding that gotos would otherwise encourage.

Or to say it another way: Dijkstra said that gotos were harmful; Wulf
asserted that mutable variables were exactly equivalent in harm to gotos
if you wrap a loop around the mutations; I now claim that for *either*
to harm you you really need both! Gotos hurt because you can get somewhere
with your global (or at least, shared-scope) variables set in who *knows*
what kind of shape; mutable variables (especially global ones) IN THE
PRESENCE OF LOOPS (iteration) have an isomorphic problem.

But by using goto-with-argument and *omitting* the shared-scope mutable
variables, the transfer of control is intimately tied to each change in
value bound to a lexical appearance of a variable. [Yes, I just realized
that I'm, rather awkwardly, describing functional programming, but I seem
to have come at it from an odd (to me) angle, and perhaps that angle might
be helpful to someone else as well...]

Finally, to circle back 'round again to the topic of "interative" versus
"tail recursive", the classic iterative solutions require mutable variables,
while the tail-recursive solutions don't *mutate* anything, they simply
create *new* bindings of the same names with the new values. For anyone who
has ever written a generational copying garbage collector, the difference
can be extremely significant! [For those not familiar, the key phrase is
"maintaining the remembered set" of objects in older generations which
point to newer generations...]

So, yes, there *are* (possibly rare) cases where the tail-recursive style
can be *more* efficient than the apparently-equivalent iterative style.


[p.s. Apologies in advance: Back from sabbatical 11/2/98, but
until then email will still get a "vacation" bounce message...]

Rob Warnock, 8L-855
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA