<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">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
cite="mid:CAEEzXAioDrGUgkg8QvGaAP4sBWoi0FxbbOhJdmqTr2cd4BB-_A@mail.gmail.com"
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 moz-do-not-send="true"
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 class="HOEnZb">
<div class="h5"><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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
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 class="gmail_signature">Beauty of style and harmony and
grace and good rhythm depend on simplicity. - Plato</div>
</div>
</blockquote>
<br>
</body>
</html>