Re: Grammatical Recursion

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

Date: 17 Dec 2004 20:45:47 GMT

Tak To <takto@alum.mit.edu.-> wrote:
...
> The difference is not in terms of storage requirement either.
> Except in special cases, both require an unbound amount of memory
> to work on unbound (arbitarily large) input. ...

Not so, at least supposing "iterative" in this discussion refers
the calculations that can be done by finite state automata,
which require no memory other than the fixed amount required
to hold their states.

> (Unconvinced? Just
> think how fast n! would overflow a 32-bit register as n grows.)

> Stack space? But a stack is just a LIFO (last in first out)
> queue. There is no reason why an iterative approach cannot use
> a LIFO.

If you allow a LIFO in "an iterative approach", then you just
lose the distinction between iterative and recursive.

> One can only talk about the difference between recursion and
> iteration in the context of specific computation models.

Yes, because that's what they are -- computation models. 

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