<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">3 is not a special case. <br>
<br>
I want to use the hanoi function with 3 pegs as a starting point.
<br>
<br>
Roelof<br>
<br>
<br>
<br>
Joel Neely schreef op 18-2-2015 om 18:11:<br>
</div>
<blockquote
cite="mid:CAEEzXAiq-PuuuaSDj26TvqtWPRga1o9=pdOz=oZUyMxxZvopCQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_default"
style="font-family:georgia,serif;font-size:small">Why is 3 a
special case?</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Feb 18, 2015 at 10:35 AM,
Roelof Wobben <span dir="ltr"><<a moz-do-not-send="true"
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">Oke,<br>
<br>
Im thinking of this way<br>
<br>
hanoi 3 source between end<br>
hanoi 1 source _ end = [ (source, end)]<br>
hanoi n source between end = hanoi (n-1) xxxx<br>
print move somehow.<br>
<br>
<br>
Roelof<br>
<br>
<br>
<br>
<br>
Dudley Brooks schreef op 18-2-2015 om 17:19:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
There are three *locations*. But there is only one
*thing* -- only *one at a time*, that is, namely whichever
one you are moving on any given move, be it a disc or an
entire stack.
<div>
<div class="h5"><br>
<br>
On 2/17/15 11:10 PM, Roelof Wobben wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
That part I understand already.<br>
<br>
The only thing I do not see is what the base case in
this exercise is because you are working with 3
things instead of 1 for example a list.<br>
<br>
As a example reversing a list recursive<br>
<br>
the base case is the not reversed list is empty.<br>
<br>
<br>
Roelof<br>
<br>
<br>
<br>
Dudley Brooks schreef op 18-2-2015 om 8:04:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
On 2/17/15 10:56 PM, Dudley Brooks wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0
0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
On 2/16/15 7:06 PM, Doug McIlroy wrote:<br>
<blockquote class="gmail_quote" style="margin:0
0 0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
<blockquote class="gmail_quote"
style="margin:0 0 0 .8ex;border-left:1px
#ccc solid;padding-left:1ex">
My way of working is one problem at the
time.<br>
So first solve the itterate one and after
that I gonna try to solve the<br>
recursion one.<br>
Otherwise I get confused.<br>
</blockquote>
This is the crux of the matter. You must
strive to think those thoughts<br>
in the opposite order. Then you won't get
confused.<br>
<br>
Recursion takes a grand simplifying view: "Are
there smaller problems of<br>
the same kind, from the solution(s) of which
we could build a solution of<br>
the problem at hand?" If so, let's just
believe we have a solver for the<br>
smaller problems and build on them. This is
the recursive step.<br>
<br>
Of course this can't be done when you are
faced with the smallest<br>
possible problem. Then you have to tell
directly how to solve<br>
it. This is the base case.<br>
<br>
[In Hanoi, the base case might be taken as how
to move a pile<br>
of one disc to another post. Even more
simply, it might be how<br>
to move a pile of zero discs--perhaps a
curious idea, but no more<br>
curious than the idea of 0 as a counting
number.]<br>
<br>
A trivial example: how to copy a list (x:xs)
of arbitrary length.<br>
We could do that if we knew how to copy the
smaller list tail, xs.<br>
All we have to do is tack x onto the head of
the copy. Lo, the recipe<br>
copy (x:xs) = x : copy xs<br>
Final detail: when the list has no elements,
there is no smaller<br>
list to copy. We need another rule for this
base case. A copy<br>
of an empty list is empty:<br>
copy [] = []<br>
<br>
With those two rules, we're done. No iterative
reasoning about<br>
copying all the elements of the list. We can
see that afterward,<br>
but that is not how we got to the solution.<br>
<br>
[It has been suggested that you can understand
recursion thus<br>
> Do the first step. Then (to put it
very dramatically)<br>
> do *everything else* in *a single
step*!<br>
This point of view works for copy, and more
generally for<br>
"tail recursion", which is trivially
transformable to iteration.<br>
It doesn't work for Hanoi, which involves a
fancier recursion<br>
pattern. The "smaller problem(s)" formulation
does work.]<br>
</blockquote>
<br>
I simplified it (or over-dramatized it) to the
point of not-quite-correctness. I was trying to
dramatize the point of how surprising the idea
of recursion is, when you first encounter it
(because I suspected that the OP had not yet
"grokked" the elegance of recursion) -- and
remembering my own Aha! moment at recursive
definitions and proofs by induction in high
school algebra, back when the only "high-level"
programming language was assembly. I see that I
gave the mistaken impression that that's the
*only* kind of recursive structure. What I
should have said, less dramatically, is<br>
<br>
Do the base case(s)<br>
Then do the recursion -- whatever steps that
might involve, including possibly several
recursive steps and possibly even several single
steps, interweaved in various possible orders.<br>
<br>
You can't *start* with the recursion, or you'll
get either an infinite loop or an error.<br>
<br>
I wouldn't quite call the conversion of
tail-recursion to iteration trivial, exactly ...
you still have to *do* it, after all! And when
I did CS in school (a long time ago), the
equivalence had only fairly recently been
recognized. (By computer language designers,
anyway. Maybe lambda-calculus mathematicians
knew it long before that.) Certainly the idea
that compilers could do it automatically was
pretty new. If it were *completely* trivial, it
would have been recognized long before! ;^)<br>
<br>
If you're younger you probably grew up when this
idea was already commonplace. Yesterday's
brilliant insight is today's trivia!<br>
</blockquote>
<br>
BTW, since, as you and several others point out,
the recursive solution of Towers of Hanoi does
*not* involve tail recursion, that's why it's all
the more surprising that there actually is a very
simple iterative solution, almost as simple to
state as the recursive solution, and certainly
easier to understand and follow by a novice or
non-programmer, who doesn't think recursively.<br>
<blockquote class="gmail_quote" style="margin:0 0
0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0
0 0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
In many harder problems a surefire way to get
confused is to<br>
try to think about the sequence of elementary
steps in the final<br>
solution. Hanoi is a good case in point.<br>
<br>
Eventually you will come to see recursion as a
way to confidently<br>
obtain a solution, even though the progress of
the computation is<br>
too complicated to visualize. It is not just a
succinct way to<br>
express iteration!<br>
<br>
Doug McIlroy<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>
</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>
<br>
</blockquote>
<br>
</blockquote>
<br>
<br>
</div>
</div>
</blockquote>
<div class="HOEnZb">
<div class="h5">
<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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Beginners mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a 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>
</body>
</html>