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.
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
[It has been suggested that you can understand recursion thus 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners