<div dir="ltr"><div class="gmail_default" style="font-family:georgia,serif;font-size:small">Instead of thinking:</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><ol><li>"Where do I move the top (smallest) disc?" and then<br></li><li>"How do I move everything else?"<br></li></ol></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">try thinking</div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_default" style="font-family:georgia,serif;font-size:small">"Where do I move the bottom (largest) disc?" along with</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">"What must happen before I move the bottom disc?" and</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">"What must happen after I move the bottom disc?"</div></blockquote><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div><div class="gmail_default" style="font-family:georgia,serif;font-size:small">-jn-</div><div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 16, 2015 at 12:45 PM, Roelof Wobben <span dir="ltr"><<a href="mailto:r.wobben@home.nl" target="_blank">r.wobben@home.nl</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>And Im still confused. <br>
<br>
Roelof<br>
<br>
<br>
<br>
Dudley Brooks schreef op 16-2-2015 om 19:41:<br>
</div><div><div class="h5">
<blockquote type="cite">
<div>Plus I should say that the "first"
(or whichever) step might also really be more than one step.
The crucial idea is that there are individual step(s) versus
"lumped" step(s), where the individual step(s) are the base
case(s) and the "lumped" step(s) are the recursive
invocation(s).<br>
<br>
On 2/16/15 10:31 AM, Dudley Brooks wrote:<br>
</div>
<blockquote type="cite">
<div>You're right, of course. I guess
the more precise way to say what I meant is that you
*separate* a single step from everything else, dealing with
everything else as a lump ... or two lumps ... or three lumps
... or ...<br>
<br>
I did at least say that "a 'single step' might have more than
one step." ;^) My mistake was the use of the word "first".<br>
<br>
On 2/16/15 5:07 AM, Joel Neely wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">I'm
sorry, but I must disagree with the generalization.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">You
described "the very nature" of a typical recursion over a
list:</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">(1) deal
with the head, then</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">(2) deal
with everything else.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">But
lists are not the only recursive structure. Infix-order
processing of a tree, for example, is more naturally
described as:</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">(1) deal
with the left sub-tree (the first "everything else"),</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">(2) deal
with the parent (analogous to the head of a list),</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">(3) deal
with the right sub-tree (the second "everything else").</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">At the
risk of a spoiler...</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">One
approach to the Towers of Hanoi problem emerges nicely
from thinking of the moves as a tree.</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small"><br>
</div>
<div class="gmail_default" style="font-family:georgia,serif;font-size:small">-jn-</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Sun, Feb 15, 2015 at 2:54 PM,
Dudley Brooks <span dir="ltr"><<a href="mailto:dbrooks@runforyourlife.org" target="_blank">dbrooks@runforyourlife.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">In my
opinion, advising Mr Wobben to watch the pattern of
moves will *not* lead him to the recursive solution,
since the pattern of moves is really iterative.<br>
<br>
My hint would be to remember the very nature of
recursion itself (for *any* problem): Do the first
step. Then (to put it very dramatically) do *everything
else* in *a single step*! (Realizing that "everything
else" is really the same problem, just made slightly
smaller.)<br>
<br>
Note: "A single step" might itself have more than one
step. My point is that recursion consists of (to put it
humorously): To do ABCDEFGHIJKLMNOPQRSTUVWXYZ, first
you do A, then you do BCDEFGHIJKLMNOPQRSTUVWXYZ. And,
of course, "first" might actually be "last"! And
remembering the story of the Gordian Knot might help
too. (I apologize that trying not to be too explicit in
the hint possibly makes it even more obscure.)<br>
<br>
Here's another hint that's useful for all kinds of
programming problems, not just recursion: Most problems
consist of not only what you're trying to solve, but
also what the restrictions are on what you're allowed to
do to solve it. Often some good insights come from
imagining how you could solve the problem if you could
ignore one or more of the restrictions (that's what I
meant by the Gordian Knot reference). So for the Towers
of Hanoi, think about what the restrictions are on what
kind of moves you're allowed to make. Remove one of
those restrictions.<br>
<br>
(Speaking of the iterative solution, the fun thing about
actually physically doing the Towers of Hanoi is that,
even though you're doing it by remembering the steps of
the iterative pattern, as you watch the towers grow and
shrink you can kind of "see" the recursion.)
<div>
<div><br>
<br>
On 2/15/15 12:51 AM, Roelof Wobben wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
YCH schreef op 15-2-2015 om 9:45:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> How about if I say
"Actually target was c not b and here is one
more<br>
disc. I put it on a. Now you should move all to
c"<br>
<br>
<br>
</blockquote>
<br>
Hanoi 1 a b c<br>
<br>
A -> C<br>
<br>
Hanoi 2 a b c<br>
<br>
A -> B<br>
A -> C<br>
B -> C<br>
<br>
Hanoi 3 a b c<br>
<br>
A -> C<br>
A -> B<br>
C -> B<br>
A -> C<br>
B -> A<br>
B -> C<br>
A -> C<br>
<br>
<br>
Roelof<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</div>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div>Beauty of style and harmony and
grace and good rhythm depend on simplicity. - Plato</div>
</div>
</blockquote>
<br>
</blockquote>
<br>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Beginners mailing list
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</div></div></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato</div>
</div>