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

[George Mills <mills@softronix.com>]

First off I never said a stack dump could not be done.
I simply said it gets "tricky".

I really don't want to get into a interative vs.
recursive debate. Recursion is a very valuable technique
for solving problems. I quite often choose a less efficient
approach to a problem if it can help make it more elegant
or easier to understand.

Choosing the right tool for the right job is an art
more than it is a science.

Some may think I'm flip flopping back and forth as to
which "camp" I'm in. I'm in both camps. I don't like it
when people strive to eliminate all MAKEs even if it
makes the code more convoluted. I also don't like
seeing iterative solutions when they are screaming to be
done recursively.

There is also nothing wrong with setting a rule to
not use MAKE to help force students to find recursive solutions
as an exercise it improving recursive problem solving
skills. In my opinion FOR or REPEAT should be frowned
upon if your going to frown upon MAKE.

Logo inherently stores data in lists and does not
use pointers etc. With lists, many problems in Logo lend
themselves to recursive solutions. There are advantages and
disadvantages to this. Lists are very powerful and
elegant in many respects. They are also often terribly
inefficient and awkward at other times.

My example in C vs Logo was to point out that they are
not so different conceptually. And I was not comparing
performance.

Chuck Shavit wrote:
> 
> 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

-- 
===============================================================
George Mills (mills@softronix.com)
http://www.softronix.com/
The www page contains some very powerful educational software.
Our single most important investment is our kids.
---------------------------------------------------------------
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.