Re: Grammatical Recursion

From: Florian Laws (fl-usenet-2004_at_void.s.bawue.de)
Date: 12/19/04 

Date: 19 Dec 2004 14:18:45 GMT

On 2004-12-18, Lee Sau Dan <danlee@informatik.uni-freiburg.de> wrote:
>>>>>> "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.

Well, computability theory doesn't care if you think of it as cheating.

Regards,

Florian

Relevant Pages

  • 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)
  • Re: counting BST nodes using iteration
    ... It uses iteration. ... size_t nodecount(node *root) { ... The problem is how to declare the stack size because we do not know ... converting the above recursion into iteration. ...
    (comp.programming)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: iterative copying of binary expression trees
    ... tail recursion as de facto optimized (bounded stack space). ... "Functional iteration" makes high sense IMHO. ... and an iterative procedure from an iterative process. ...
    (comp.lang.lisp)
  • Re: counting BST nodes using iteration
    ... without using recursion. ... It uses iteration. ... delete stack. ... If you have a decent stack ADT, ...
    (comp.programming)