Re: Grammatical Recursion

From: Lee Sau Dan (danlee_at_informatik.uni-freiburg.de)
Date: 12/18/04 

Date: 18 Dec 2004 23:25:26 +0800

>>>>> "Florian" == Florian Laws <fl-usenet-2004@void.s.bawue.de> writes:

    [Ackerman function]
>> To rewrite this "iteratively" would surely involve
>> hand-management of a stack, which might as well be recursion.

    Florian> I does, but that only shows that Iteration is in fact
    Florian> just as powerful as Recursion.

Using a stack in an iteration cheats by adding recursive power to it,
thereby upgrading it to recursion. The additional power of recursion
over iteration lies in the (implicit) unbounded stack. 

-- 
Lee Sau Dan                     §õ¦u´°                          ~{@nJX6X~}
E-mail: danlee@informatik.uni-freiburg.de
Home page: http://www.informatik.uni-freiburg.de/~danlee

Relevant Pages

  • Re: Grammatical Recursion
    ... Florian> just as powerful as Recursion. ... >> Using a stack in an iteration cheats by adding recursive power ...
    (sci.lang)
  • Re: Any use for recursion?
    ... In modern languages there is no overhead. ... popped back off the stack, the program counter being changed again. ... Recursion is ubiquitous in modern software. ...
    (comp.programming)
  • Re: Memory management strategy
    ... >>trading memory for speed ... The use of registers instead of the stack doesn't need inlining. ... >longer instructions to access smaller data than they were optimized for. ... square) but it didn't need recursion or some kind of stack. ...
    (comp.lang.c)
  • Re: grassfire algorithm in java
    ... > How many recursions did it take to overflow the stack? ... > say, recursion counting does. ... For debugging it MAY be a useful technique - but you are talking about using ...
    (comp.lang.java.programmer)
  • Re: Is this tai-recursion?
    ... There is no difference between tail-recursion and iteration. ... That's why tail-recursion is so simple, ... fetch next instruction from instruction pointer ... instructions will manipulate the processor stack. ...
    (comp.lang.scheme)