Recursion – The Towers of Hanoi (iii)

Solving the ToH for one disc, or even two discs is trivial (moving from tower A to C, using B as the intermediary). For two disks we move the smaller top disc to B, the larger bottom disc to C, and then the smaller disc on B to C. This takes three moves. Moving three discs takes a bit more effort. However we already know how to move 2 discs, so the problem can be restated in terms of an existing solution. Move the top two discs in the tower from A to B. Then move the third disc from A to C, and finally move the two disc stack from B to C. What about if we had four discs… well we know hot to move 3 discs, so… well you get the idea. Here is a visual depiction on how 3 discs can be moved.

Fig. 1: The seven moves required to solve the 3-disc T0H

We can then solve the Towers of Hanoi problem for a stack of discs of height n, by trying to solve it for a stack of height n−1. To solve for a stack of height n−1, we try to solve for a stack of height n−2, etc. Now this can be easily solved using a recursive algorithm, because each smaller stack is a sub-problem of the original. To move n discs from tower A to tower C, using tower B as the intermediary, a rudimentary algorithm would look like this:

  1. Move n−1 discs from A to B.
  2. Move one disc from A to C.
  3. Move n−1 discs from B to C.

From this a more definitive recursive algorithm can be formulated, again moving a tower from A to C using B as the intermediary:

PROCEDURE moveDiscs(N,A,C,B)
BEGIN
   IF N > 1 THEN
      moveDiscs(N-1,A,B,C)
      move the top disc from tower A to tower C
      moveDiscs(N-1,B,C,A)
   END IF
END

Here is a basic C function, called moveR() to perform the ToH recursively (towers A, B, and C, have been replaced with the more descriptive from, to, using.

void moveDiscs(int N, int from, int to, int using) {
   if (N > 0) {
      moveDiscs(N-1, from, using, to);
      printf("move %d -> %d\n", from, to);
      moveDiscs(N-1, using, to, from);
   }
}

One way of deciphering this is to lay out each level of the recursion as it proceeds, basically tracing the recursive process. If the function above is called as moveDiscs(3,1,3,2), it would move 3 discs from tower 1 (A), to tower 3 (C), using tower 2 (B) as the intermediary.

The various “L” labels specify the level of recursion, the numbers ❶→❼ coincide with the example diagram in Fig.1. The STOP sign shows where the function is called recursively, but terminates, signifying that it cannot recurse deeper. In all, although there are only 7 moves (shown in blue) for 3 discs, there are actually 15 recursive calls, albeit 8 are terminations.

One thought on “Recursion – The Towers of Hanoi (iii)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.