How does recursive algorithm work for Towers of Hanoi?

Question

This is code from a book I have explaining recursion. The problem is that I don't understand the steps taken by the program:

var hanoi = function(disc,src,aux,dst) {
    if (disc > 0) {
        hanoi(disc - 1,src,dst,aux);
        document.write("Move disc " + disc + " from " + src + " to " + dst + "<br />");
        hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

This is how the Output reads:

Move disc 1 from src to dst
Move disc 2 from src to aux
Move disc 1 from dst to aux
Move disc 3 from src to dst
Move disc 1 from aux to src
Move disc 2 from aux to dst
Move disc 1 from src to dst

Can someone break this down step by step? It would be very helpful to me.

Answer 1

Probably the simplest solution to the Towers of Hanoi works like this:

To move x discs from peg A to peg C, using peg B as an "aux" peg:

1. Move x-1 discs from peg A to peg B, using peg C as the aux peg.
2. Move the x'th disc from peg A to peg C (no aux peg needed, cause you're only moving one disc).
3. Move the x-1 discs from peg B to peg C, using peg A as the aux peg.

Note that in order to move x discs, you have to move x-1 discs. You can just use the same function to move those x-1 discs, and just switch which pegs are the source, dest, and aux pegs. That's what makes Towers of Hanoi such a common example of recursion, and that's the kind of pattern you need to see in a problem in order to make recursion work for you. It need not be "move x-1 discs", of course...it could be something like "list this subfolder". Trees (like a directory with subfolders and such) are another place where recursion shines. As do other jobs where in order to do the job on an item, you may need to do the same job on sub-items.

Now, in order to have useful recursion, you need a "base case" -- a condition where the recursion will stop. If you don't, the code will run forever (or at least til it runs out of memory or overflows the call stack). The base case here occurs when x == 0 (since moving 0 discs means you do nothing, due to the if around the meat of the function). It could also be when x == 1, as then you don't have to recurse, but the extra if before each hanoi call would add a bit of noise (and the main benefit to a recursive solution is its simplicity). Anyway, when x == 0, the function returns without doing anything. The function that called it (which had x == 1) now gets to continue doing its thing -- in this case, saying "move disc 1 from src to dest", and then calling the hanoi function again with the args switched.

The flow goes a bit like this:

hanoi(3, src, aux, dest)
  hanoi(2, src, dest, aux)
    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "Move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

    print "Move 2 from src to aux"

    hanoi(1, dest, src, aux)
      hanoi(0, dest, aux, src)        // no op
      print "move 1 from dest to aux"
      hanoi(0, src, dest, aux)        // no op

  print "move 3 from src to dest"

  hanoi(2, aux, src, dest)
    hanoi(1, aux, dest, src)
      hanoi(0, aux, src, dest)        // no op
      print "Move 1 from aux to src"
      hanoi(0, dest, aux, src)        // no op

    print "Move 2 from aux to dest"

    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op