[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: to big nest level of recursion
From: |
David Kastrup |
Subject: |
Re: to big nest level of recursion |
Date: |
Sat, 25 Mar 2006 12:46:40 +0100 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) |
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