Re: Grammatical Recursion

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

Date: Fri, 17 Dec 2004 12:42:29 -0500

Lee Sau Dan wrote:
> Recusive, not iterative. Iteration simply loops. There is no
> self-reference. Recursion has self-reference. That's the main
> difference.

While we are in the nit-picking mode ;-), let me point out that
recursion does not necessarily involve self-reference. In pure
lambda calculus, there is no self-reference. (Loosely speaking,
the 'self' is regenerated every time.)

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. (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.

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

:-)

Tak 

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