[Haskell-beginners] tower hanoi problem

[Dudley Brooks]

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!

> 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