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