|
![](/i/fill.gif) |
Warp wrote:
> From a programmer's point of view, simplified: The Ackermann's function
> is an example of a function which cannot be computed iteratively, but must
> be computed recursively.
>
> This proves by example that not all algorithms can be implemented
> iteratively.
>
> (And "iteratively" in this context means "only requires O(1) memory to
> compute the algorithm".)
Mmm, I see. Yes, the third identity requires you to either recurse twice
(requiring more stack), or to build a table of results to avoid the
extra recursion (also requiring more memory).
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |