[Haskell-beginners] tower hanoi problem

[Roelof Wobben]

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
>