Crockford's hanoi function (from "The Good Parts")

Question

Hi,

at the moment I'm reading Douglas Crockford's book, and the towers of hanoi function is a bit over my head. Even with logging stuff to the console I wasn't able to really understand what's going on. Here's the function with my additions:

var hanoi = function (disc, src, aux, dst) {
  console.log(disc);
  console.log(src, dst);    
  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
    console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

This results in the following:

3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
Move disc 1 from Src to Dst
0
Aux Dst
Move disc 2 from Src to Aux
1
Dst Aux
0
Dst Src
Move disc 1 from Dst to Aux
0
Src Aux
Move disc 3 from Src to Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
Move disc 1 from Aux to Src
0
Dst Src
Move disc 2 from Aux to Dst
1
Src Dst
0
Src Aux
Move disc 1 from Src to Dst
0
Aux Dst

And I'm lost at an early point. At line 6 of the results, how can it go back from Src Aux to Src Dst?

And how can the number of discs go up again once it has reached 0, when the function is only calling itself using "disc - 1"?

Thanks in advance!

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

Answer 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 smaller disk on a larger 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.