Tracy R Reed wrote:
Also, iteration is *by definition* O(1) in space. That is not true
for generalized recursion; it is true only for tail recursion.
Right. Fortunately most of the commonly used types of iteration can
be implemented in a tail recursive way.
I'm not convinced. Common Lisp explicitly avoided making tail recursion
part of the standard. I don't know if they are right or wrong, but I'm
not willing to completely discount some really smart people.
And really, tail recursion is iteration as far as the control flow of
the machine language goes
I'm pretty sure that's not true. It's more like a stack entry that
keeps getting pitched into the trash. However, there are some fairly
deep subtleties (and I can't even begin to explain them).
If you really want to know what's going on at a very deep level, you
really need to take some time and read "Lisp in Small Pieces".
Warning: It's a *very* dense book and a very slow read.
In addition, go take a look at Okasaki's "Purely Functional Data
Structures". It is *not* always easy to interconvert. In fact, you
often can't even prove some of the O() bounds.
Again, a very dense book. *Very* hard to dig through.
Perhaps. Haskell has something called a state monad. I'm not sure how
it works yet but it might be one way to help out that situation.
Sure, but then you are effectively back at iteration.
-a
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
