Re: to big nest level of recursion

[David Kastrup]

Alan Mackenzie <acm@muc.de> writes:

> David Reitter <david.reitter@gmail.com> wrote on Tue, 21 Mar 2006
> 21:31:29 +0000:
>
> [ .... ]
>
>> Maybe it's a consolation for you that for every recursive algorithm,
>> you can formulate an iterative version. And you don't bloat a call
>> stack when you do so.
>
> This is not true.  There are algorithms that are intrinsically
> recursive and cannot be formulated with mere iteration (such as the
> Ackermann function, specially invented to demonstrate this).

They cannot be formulated with iteration _without_ a stack.  But of
course, when using a stack as a data structure, you can map any
recursion onto iteration.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum