LOGO-L> Recusrion vs. Iteration (was: QUESTION ON CONDITIONAL OUTPUTS)

[Chuck Shavit <CShavit@MagicSquare.com>]

At 11:28 AM 4/26/98 -0400, George Mills wrote:
>There are plenty of legitimate situations where complex
>recursion can be used that will output "complex"
>stack dumps and is not a demonstration of being
>overkill.
>
>Also a lot of folks generalize that recursion only exists
>if the calling the procedure calls itself. I think
>some of the most interesting examples of recursion are
>when procedure a, calls b, calls c, which then calls a.
>Heuristics would again get tricky. A good example of
>this is parsing expressions.

You're right.  But heuristics are just that: solutions for a limited class
of problems which occur most of the time.  And BTW, there are standard ways
of collapsing a series of "ABCABCABC..." to "ABC x 100", but I would not
even bother  to solve this problem, for practical reasons.

>Going slightly off topic:
>
>Also keep in mind that you can have deep recursion
>in UCBLogo/MSWLogo that is detecteed as tail recursive
>which is just as therectically efficient as iterative
>solutions and is just an alternive interative syntax.
>
>Think of the common example in C where folks do
>something like.
>
>for (pointer=&things;pionter!=null;pointer=pointer.next)
>  {
>  do stuff with pointer
>  }
>
>And in logo
>
>to do_stuff :things
>  if emptyp :things [stop]        ; pointer != null
>  do something with first :things ; do stuff
>  do_stuff butfirst :things       ; pointer=pointer.next
>end

Of course if you are careful, you can implement a tail-recursion algorithm
which is not terribly more expensive than iteration.  It will always be
less efficient, though -- in your example you had to call two functions
(do_stuff & butfirst) in each iteration, pass them arguments and return a
value.  And, in many cases, it will also be less clear and more error prone
than a for-loop style iteration.  When I see a Lisp/LOGO compiler which
compiles your LOGO algorithm into something as efficient as your C
algorithm, I will have to take my words back...

The main disagreement I have with people of the traditional LOGO/Lisp
school is when they prefer recursion over iterations even when it is very
expensive.  I guess it has to do with Brian's science vs. engineering
education thing.  An excellent example is actually the original ADDLISTS
function:

  * Adding two vectors (into a third vector) should have an O(n)
complexity, but with recursion ADDLISTS is at least O(n^2) because you have
to keep allocating and deallocating lists and CONSing them together.

  * The recursive algorithm is more cumbersome and therefore more error
prone and hard to debug than a one-line iterations.  This is probably why
the original post was made in the first place.  

  * Heuristics exist for reducing the inefficiency of recursive algorithms.
 The two example above are tail recursion and BUTFIRST (which depending on
the implementation might return a CDR pointer instead of a new list with
n-1 elements).  But one has to know how to use them carefully.

Granted, LOGO's syntax needs to be enhanced a bit to make it easy to write
iterative algorithms, but I think it can be fixed if people believe that
the two alternatives should be available even (especially) to beginners.  


Chuck Shavit
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.