Subject: Re: CL implementations and tail-call optimization
From: (Rob Warnock)
Date: Tue, 31 Oct 2006 23:16:54 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Thomas A. Russ <> wrote:
| writes:
| > Is it possible, even in theory, to convert a NON-tail recursive
| > procedure to an iterative process?
| There are, however, certain functions that are fundamentally recursive
| in nature (such as tree walks) which you can't convert into iterative
| processes, simply because they are beyond the computational power of
| non-recursive functions.

Not true. As Pascal showed in a parallel reply, tree-walks
can easily be converted to iteration using an explicit stack.

Such iteration+stack *is* the general solution: how else would
you write "recursive" functions on a CPU that didn't *have* a
recursive function call instruction?!?  ;-}  E.g., the DEC PDP-8
subroutine call was about as NON-recursive as you can get -- it
*stored* the return address *into* the first location of the
called routine! Yet people wrote Algol compilers [and other
languages with recursion] that ran just fine on a PDP-8.


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607