Thomas A. Russ <tar@sevak.isi.edu> wrote:
+---------------
| sankymoron@gmail.com 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

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607