<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">(I hope that no one will think that
this is too much of a hint.)<br>
<br>
There are three restrictions on how you can move:<br>
<br>
(1) You can only move one disc at a time.<br>
<br>
(2) You can only move the top disc of a stack.<br>
<br>
(3) You can't put a larger disc on a smaller one.<br>
<br>
What if (1) weren't true? What if you could move a whole bunch of
discs at the same time? (Which would kind of mean that (2) wasn't
true either.) What if, after you had removed a certain number of
discs (I won't say how many, but think small!) from the top of a
stack, you could simply pick up the entire remaining stack and
move it?<br>
<br>
On 2/16/15 10:45 AM, Roelof Wobben wrote:<br>
</div>
<blockquote cite="mid:54E23AD4.8050203@home.nl" type="cite">
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
<div class="moz-cite-prefix">And Im still confused. <br>
<br>
Roelof<br>
<br>
<br>
<br>
Dudley Brooks schreef op 16-2-2015 om 19:41:<br>
</div>
<blockquote cite="mid:54E239DA.1010606@runforyourlife.org"
type="cite">
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
<div class="moz-cite-prefix">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 cite="mid:54E23764.4030203@runforyourlife.org"
type="cite">
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
<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>
</blockquote>
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Beginners mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>