Some time has elapsed since the last post where I recommended to read The Little Schemer. If you've read The Little Schemer, then you've encountered recursion in new and exciting ways from the old and familiar ideas of arithmetic. Your mind now is ready to continue exploring more recursion. Here we introduce the classical problem of the Towers of Hanoi.

The problem is setup with three pegs and all N discs with a hole in the center placed in one source peg ordered from top to bottom in ascending order of diameter. The goal is to be able to move all discs from the source peg to the destination peg while keeping the two constraints that we move one disc at a time and that a larger disc cannot be placed on top of a smaller disk.

To solve the problem, we must be able to divide the problem into subproblems. What we do first is find a way to take the first N-1 discs on top from source and move them all to the auxiliary peg while using the destination peg as we need it to keep the constraints from being violated. Once all the top N-1 discs are correctly stacked in the auxiliary peg, we then move from the source peg the bottom-most disc with largest diameter to the destination peg. The third step then is to move the stack from the auxiliary peg to the destination peg using the source peg as needed to avoid violating the constraints as we move discs.

Below is JavaScript code that spells out the recursive solution to the Towers of Hanoi puzzle. Our source, auxiliary, and destination pegs are described as src, aux, and dst in the code of our hanoi function. Line 3 is what we do to complete our first subproblem, Line 4 is what we do to move the bottom disc to the destination peg, and Line 5 is what we do to complete our third subproblem of moving all remaining disc from the auxiliary peg to the destination peg while using the source peg to ensure we do not violate the constraints.

1
2
3
4
5
6
7

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

If you view the image of this post you will see recursion in action for when there are 3 discs, and three pegs src, aux, and dst. The labels 1 to 3 in the image take care of the first subproblem; label 4 moves the bottom disc from src to the destination peg; and labels 5 to 7 take care of the third subproblem of moving the sub-stack from the auxiliary peg to the destination peg. You'll need to view the image separately in your browser window to see these labels clearly. Just hover your mouse over the image, right click the mouse, and then click "View Image". The output of hanoi when N is 3 is the printout of labels 1 to 7.