Re: Grammatical Recursion

From: Tak To (takto_at_alum.mit.edu.-)
Date: 12/20/04 

Date: Mon, 20 Dec 2004 09:27:49 -0500

Tak To <takto@alum.mit.edu.-> wrote:
> One can only talk about the difference between recursion and
> iteration in the context of specific computation models.

Greg Lee wrote:
> Yes, because that's what they are -- computation models.

That was not what I meant. Sorry, my bad. I should have said
"formalism" in instead of "model" to avoid the confusion.
Recursion and iteration are different types (or idioms) of
algorithms in a formalism. For the term "recursion" to be
meaningful, the formalism must have some notion of "function",
"invocation", etc; and for "iteration" to be meaningful, the
formalism must have "loop", "repeat", etc. The formalism
defined by a high level programming language such as "C"
would have both; so does Kleene Recursive Functions with
its mu operator. However, formalisms such as the Turing
Machine, Lamdba Calculus, or machine instruction sets without
stack operations do not have either (or only one of them);
and comparing iteration and recursion in the context of these
formalisms would be rather meaningless. In particular, in
the Post (after Emil Post) Production System (which forms the
basis of mathematical language processing as well as the
programming language SNOBOL), there is really no notion of
iteration, and only a weak notion of recursion -- in the sense
that a grammar can be _recursive_ (meaning that a production
of a symbol can reference the symbol itself). Thus, IMHO,
comparing iteration and recursion in this context is rather
meaningless.

Tak 

--
----------------------------------------------------------------+-----
Tak To                                            takto@alum.mit.eduxx
--------------------------------------------------------------------^^
  [taode takto ~{LU5B~}]      NB: trim the xx to get my real email addr

Relevant Pages

  • 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: 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)
  • Re: Multivalue tail recursion?
    ... programmers. ... Lisp with the idea of using recursion for everything, ... If you don't need to prove properties of your programs, you can ignore such considerations - then iteration constructs are typically easier to read. ...
    (comp.lang.lisp)
  • Re: Defence of recursive programming
    ... less fundamental) than either iteration than recursion. ... depending on whether you're first-time into the loop or in a ... Robinson about recursive tree traversals, ...
    (comp.lang.functional)