[Haskell-beginners] tower hanoi problem

[Joel Neely]

I'm sorry, but I must disagree with the generalization.

You described "the very nature" of a typical recursion over a list:
(1) deal with the head, then
(2) deal with everything else.

But lists are not the only recursive structure. Infix-order processing of a
tree, for example, is more naturally described as:
(1) deal with the left sub-tree (the first "everything else"),
(2) deal with the parent (analogous to the head of a list),
(3) deal with the right sub-tree (the second "everything else").

At the risk of a spoiler...

.

.

.

.

One approach to the Towers of Hanoi problem emerges nicely from thinking of
the moves as a tree.

-jn-

On Sun, Feb 15, 2015 at 2:54 PM, Dudley Brooks <dbrooks at runforyourlife.org>
wrote:

> 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.
>
> 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.)
>
> 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.)
>
> 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.
>
> (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.)
>
>
> On 2/15/15 12:51 AM, Roelof Wobben wrote:
>
>> YCH schreef op 15-2-2015 om 9:45:
>>
>>> How about if I say "Actually target was c not b and here is one more
>>> disc. I put it on a. Now you should move all to c"
>>>
>>>
>>>
>> Hanoi 1 a b c
>>
>> A -> C
>>
>> Hanoi 2 a b c
>>
>> A -> B
>> A -> C
>> B -> C
>>
>> Hanoi 3 a b c
>>
>> A -> C
>> A -> B
>> C -> B
>> A -> C
>> B -> A
>> B -> C
>> A -> C
>>
>>
>> Roelof
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>



-- 
Beauty of style and harmony and grace and good rhythm depend on simplicity.
- Plato
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150216/0748a59a/attachment.html>