Re: Grammatical Recursion

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

Date: 18 Dec 2004 11:25:37 GMT

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"?

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

Regards,

Florian

Relevant Pages

  • Re: Grammatical Recursion
    ... Jacques> equivalent, insofar as anything you do through recursive ... you can do through simple iteration ... iteration is insufficient and recursion is needed. ... >> patterns as recursive. ...
    (sci.lang)
  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: Grammatical Recursion
    ... Jacques Guy writes: ... >> As you say, recursion is not equivalent to iteration, contrary to ... which might as well be recursion. ... "he structural trend in linguistics which took root with the ...
    (sci.lang)
  • Re: Simple recursive functions in Lisp
    ... (labels ((rev (lst acc) ... becomes a loop variable. ... to the naive car/cdr recursion). ... Another way to express Graham's algorithm is iteration. ...
    (comp.lang.lisp)
  • 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)