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

Question

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"?

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.