[Haskell-beginners] tower hanoi problem

[Doug McIlroy]

> 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.]

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