Re: Grammatical Recursion

From: Greg Lee (greg_at_ling.lll.hawaii.edu)
Date: 12/18/04 

Date: 18 Dec 2004 13:03:10 GMT

Florian Laws <fl-usenet-2004@void.s.bawue.de> wrote:
> On 2004-12-18, Lee Sau Dan <danlee@informatik.uni-freiburg.de> wrote:
> >>>>>> "Jacques" == Jacques Guy <jguy@alphalink.com.au> writes:
> >
> > Jacques> Lee Sau Dan wrote:
> > >> Sigh... you confuse iteration with recursion...
> >
> > Jacques> No I don't. I have made it clear that any recursive
> > Jacques> function can be rewritten as an iteration.
> >
> > If you haven't mixed up the two, then you MUST be wrong. There are
> > languages that can be generated by a recursive grammar, but not an
> > iterative one.

> What is an "iterative grammar"?

A phrase structure grammar of type 3 in the Chomsky hierarchy, whose
rules have on the right a terminal followed by at most one non-terminal.

> Regardless, any algorithm using recursion can be converted in one using
> iteration, with the help of using an explicit stack, if necessary.

True, but it's the use of a stack, explicit or implicit, that distinguishes
iterative from recursive (as those terms have come to be used in this
discussion). Making an implicit stack explicit doesn't change the
type of the algorithm. 

-- 
Greg Lee <greg@ling.lll.hawaii.edu>

Relevant Pages

  • Re: [PATCH] Introduce nodemask_t ADT [0/7]
    ... I know that a richer repertoire of operations will reduce the stack ... > it calls change things, and which don't, letting it pass a pointer to ... make sense to pass it by reference. ... > If one needs an explicit call by reference to avoid passing a multi-word ...
    (Linux-Kernel)
  • Re: DO loop standards question.
    ... > integer type of the control variable is non-conforming? ... interp that prompted the more explicit wording - I forget). ... The standard says that the iteration count is computed ... symptoms like making the loop infinite). ...
    (comp.lang.fortran)
  • 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: Recursive functions Vs Non-recursive functions - performance aspect
    ... Conversion to iteration does not help here. ... In the conversion, you definitely have to maintain your own stack. ... Some recursive algorithms can be ...
    (comp.lang.c)
  • Re: [GIT PULL] x86/paravirt for v2.6.33
    ... In the case of 'ptrace' we control the stack of the tracee. ... but I _am_ saying that system calls that depend on ... task_pt_regsare fundamnetally fragile and broken, and have subtle ... if you make it very explicit that the system call gets passed ...
    (Linux-Kernel)