[Haskell-beginners] tower hanoi problem

Joel Neely joel.neely at gmail.com
Wed Feb 18 17:11:18 UTC 2015 

Why is 3 a special case?

On Wed, Feb 18, 2015 at 10:35 AM, Roelof Wobben <r.wobben at home.nl> wrote:

> Oke,
>
> Im thinking of this way
>
> hanoi 3 source between end
> hanoi 1 source _ end = [ (source, end)]
> hanoi n source between end = hanoi (n-1) xxxx
>                                                         print move somehow.
>
>
> Roelof
>
>
>
>
> Dudley Brooks schreef op 18-2-2015 om 17:19:
>
>> 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.
>>
>>
>> On 2/17/15 11:10 PM, Roelof Wobben wrote:
>>
>>> That part I understand already.
>>>
>>> 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.
>>>
>>> As a example reversing a list recursive
>>>
>>> the base case is the not reversed list is empty.
>>>
>>>
>>> Roelof
>>>
>>>
>>>
>>> Dudley Brooks schreef op 18-2-2015 om 8:04:
>>>
>>>> On 2/17/15 10:56 PM, Dudley Brooks wrote:
>>>>
>>>>> On 2/16/15 7:06 PM, Doug McIlroy wrote:
>>>>>
>>>>>> My way of working is one problem at the time.
>>>>>>> So first solve the itterate one and after that I gonna try to solve
>>>>>>> the
>>>>>>> recursion one.
>>>>>>> Otherwise I get confused.
>>>>>>>
>>>>>> This is the crux of the matter. You must strive to think those
>>>>>> thoughts
>>>>>> in the opposite order. Then you won't get confused.
>>>>>>
>>>>>> Recursion takes a grand simplifying view: "Are there smaller problems
>>>>>> of
>>>>>> the same kind, from the solution(s) of which we could build a
>>>>>> solution of
>>>>>> the problem at hand?" If so, let's just believe we have a solver for
>>>>>> the
>>>>>> smaller problems and build on them. This is the recursive step.
>>>>>>
>>>>>> Of course this can't be done when you are faced with the smallest
>>>>>> possible problem. Then you have to tell directly how to solve
>>>>>> it. This is the base case.
>>>>>>
>>>>>> [In Hanoi, the base case might be taken as how to move a pile
>>>>>> of one disc to another post. Even  more simply, it might be how
>>>>>> to move a pile of zero discs--perhaps a curious idea, but no more
>>>>>> curious than the idea of 0 as a counting number.]
>>>>>>
>>>>>> A trivial example: how to copy a list (x:xs) of arbitrary length.
>>>>>> We could do that if we knew how to copy the smaller list tail, xs.
>>>>>> All we have to do is tack x onto the head of the copy. Lo, the recipe
>>>>>>     copy (x:xs) = x : copy xs
>>>>>> Final detail: when the list has no elements, there is no smaller
>>>>>> list to copy. We need another rule for this base case. A copy
>>>>>> of an empty list is empty:
>>>>>>     copy [] = []
>>>>>>
>>>>>> With those two rules, we're done. No iterative reasoning about
>>>>>> copying all the elements of the list. We can see that afterward,
>>>>>> but that is not how we got to the solution.
>>>>>>
>>>>>> [It has been suggested that you can understand recursion thus
>>>>>>     > Do the first step.  Then (to put it very dramatically)
>>>>>>     > do *everything else* in *a single step*!
>>>>>> This point of view works for copy, and more generally for
>>>>>> "tail recursion", which is trivially transformable to iteration.
>>>>>> It doesn't work for Hanoi, which involves a fancier recursion
>>>>>> pattern. The "smaller problem(s)" formulation does work.]
>>>>>>
>>>>>
>>>>> 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
>>>>>
>>>>>     Do the base case(s)
>>>>>     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.
>>>>>
>>>>> You can't *start* with the recursion, or you'll get either an infinite
>>>>> loop or an error.
>>>>>
>>>>> 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! ;^)
>>>>>
>>>>> If you're younger you probably grew up when this idea was already
>>>>> commonplace.  Yesterday's brilliant insight is today's trivia!
>>>>>
>>>>
>>>> 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.
>>>>
>>>>>
>>>>>  In many harder problems a surefire way to get confused is to
>>>>>> try to think about the sequence of elementary steps in the final
>>>>>> solution. Hanoi is a good case in point.
>>>>>>
>>>>>> Eventually you will come to see recursion as a way to confidently
>>>>>> obtain a solution, even though the progress of the computation is
>>>>>> too complicated to visualize. It is not just a succinct way to
>>>>>> express iteration!
>>>>>>
>>>>>> Doug McIlroy
>>>>>> _______________________________________________
>>>>>> 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
>>>>
>>>>
>>>
>>
>>
> _______________________________________________
> 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/20150218/17d1b3cd/attachment.html>

More information about the Beginners mailing list