Crockford's Hanoi Function (from "the Good Parts")
Solution 1:
The confusion arises because the text representation of the output isn't the best way to understand recursion. The number of discs isn't "going up", rather it's hanoi(1) that continues to run once hanoi(0) is done.
I've created a modified example at JSBin that prints the output in a (somewhat) prettier way with spaces. Only the "moves" actually do anything, the rest of the lines are just recursive calls to solve smaller sub-problems in order to tackle the entire problem later.
You might also want to have a look at this Java applet that graphically shows how the algorithm works - this might be easier to understand.
Solution 2:
Towers of Hanoi is an excellent example of how recursion can simplify a given problem. The idea is as follows: you have to move N disks from a source stack to a destination stack, one disk at a time and you can never put a larger disk on a smaller one. You can use an auxiliary stack. Let's say N = 10. You have no idea how to solve it. But you can make the problem simpler (you hope):
move 9 disks to the auxiliary stack,
move the remaining(and largest!) disk to the destination stack, and
move the 9 disks from the auxiliary stack to the destination stack
Again, you have no idea how to move a 9 disk stack, but that's no problem either:
move 8 disks from the auxiliary stack to the source stack,
move the remaining disk to the destination stack (there are 2 disks now), and
move the 8 disks from the source stack to the destination stack
Repeat this until the stack you have to move is only 1 disk big.
About the number of disks going up again: you call the function recursively for N-1 disks, which in the function is assigned to N. This N only exists until the function ends, and returns to the previous level. Then you get the old value of N again.
Post a Comment for "Crockford's Hanoi Function (from "the Good Parts")"