Getting Your Head Around Tower of Hanoi

In these past few days I have been learning recursion in attempt of refreshing my algorithms knowledge. Tower of Hanoi is an interesting practical example of recursion. Only after few hours today, thanks to this video, I can quite grasp the concept of it better. I am writing it here for my own reference.

As wikipedia description, Tower of Hanoi is mathematical game/puzzle. The game consists of 3 rods, we can call it left (L), center (C) and right (R).

In each rod we can 1 or more pegs. The goal of the game is to move pegs from L to R. However there are some restrictions:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

Let us see the simplest example. Tower of hanoi with only one peg.

Initial State Tower of Hanoi of 1 Peg

Since there is only one peg, we can just immediately move it from L to R.

Final State Tower of Hanoi of 1 Peg

I am going to use this following notation to describe the step in Tower of Hanoi: <step number>: <peg>, <from>, <to>. Peg will be numbered from 1 to n, where 1 is the smallest peg and n is the largest peg. For first example above, the final state of the tower can be achieve only in 1 step:

1: 1, L, R // move peg number 1 from L to R

Next is example of Tower of Hanoi with 2 pegs:

Initial State Tower of Hanoi of 2 Pegs.

Step 1

Step 2

Step 3

Steps taken for Tower of Hanoi with 2 pegs described above:

1: 1, L, C
2: 2, L, R // largest peg 
3: 1, C, R

Next I will directly present steps needed for Tower of Hanoi with 3 pegs:

1: 1, L, R
2: 2, L, C
3: 1, R, C
4: 3, L, R // largest peg
5: 1, C, L
6: 2, C, R
7: 1, L, R

Then 4 pegs steps:

 1: 1, L, C
 2: 2, L, R
 3: 1, C, R
 4: 3, L, C
 5: 1, R, L
 6: 2, R, C
 7: 1, L, C
 8: 4, L, R // largest peg
 9: 1, C, R
10: 2, C, L
11: 1, R, L
12: 3, C, R
13: 1, L, C
14: 2, L, R
15: 1, C, R

Although might not be immediately visible, but steps taken for Tower of Hanoi with more pegs consists step taken for fewer pegs Tower of Hanoi.

1: 1, L, R // move largest peg from left to right

Step number two in 2 pegs tower of Hanoi below, basically same like step number 1, in 1 peg Tower of Hanoi above. In 1 peg tower, largest peg is peg number 1 and therefore in 2 pegs tower, largest peg is peg number 2. If scroll up to 3 pegs tower, we also can see peg number 3 will be moved directly from left to right.

1: 1, L, C
2: 2, L, R // move largest peg from left to right
3: 1, C, R

Looking from 2 pegs tower above, there is also important step that always happen for Tower of Hanoi that has more than 1 peg. We need to move peg to 'parking' rod to honour the restriction of No disk may be placed on top of a smaller disk.

1: 1, L, C // park peg 1 from L to C
2: 2, L, R // move directly largest peg to final destination R
3: 1, C, R // move peg 1 from parking rod to final destination

To give a stronger example, for 3 pegs tower below, the pegs movement consists movement that happens in 2 pegs and 1 peg tower.

Step 1 to 3 are like 2 pegs movement. These 3 steps will try to park peg 1 and 2 from L to C
1: 1, L, R
2: 2, L, C
3: 1, R, C
at the end of step three, peg 1 and 2 will be parked temporary on rod C

4: 3, L, R // this is like 1 peg movement directly from L to R from source to destination

Step  5 to 7 are like 2 pegs movement as well. These 3 steps will take peg 1 and 2 that was parked at rod C to rod R the destination.
5: 1, C, L
6: 2, C, R
7: 1, L, R

Observing from its characteristic we can derive the Tower of Hanoi algorithms. For input we have number of pegs n, start rod which we assign to L, destination R rod and parking C rod. The signature of the method will look like this:

void towerOfHanoi(int n, char start, char destination, char parking);

As recursive algorithms, we need to know the base case, which it will be when peg number 1 is passed to the method.

void towerOfHanoi(int n, char start, char destination, char parking) {
  if (n == 1) { // the base case
    System.out.println(String.format("%d, %c, %c", n, start, dest));
  } else {
    // recursive block
  }
}

By only having base case above, we can try to call the method with only 1 peg:

towerOfHanoi(1, 'L', 'R', 'C');
output:
1, L, R

However we couldn't call the method for n > 1 because we haven't implement the recursive block.

I am pasting the 2 pegs movement again here, to help us implement the recursive block.

1: 1, L, C
2: 2, L, R 
3: 1, C, R

In n pegs of tower of hanoi, step 1 is when we move peg (n-1) from start to parking (parking becomes destination). Step 2 to move peg n from start to destination. Step 3 to move peg (n-1) from parking to destination. This can help us implement the recursive block of unfinished method above.

void towerOfHanoi(int n, char start, char destination, char parking) {
  if (n == 1) { // the base case
    System.out.println(String.format("%d, %c, %c", n, start, destination));
  } else {
    towerOfHanoi(n - 1, start, parking, destination); // move to parking
    System.out.println(String.format("%d, %c, %c", n, start, destination));
    towerOfHanoi(n - 1, parking, destination, start); // take the peg from parking to destination
  }
}

It will take sometime to get your head around recursion such as this Tower of Hanoi example but it will be an enjoyable journey. Although I aim this for my own personal note, I will be grateful if others can find this useful.