The Tower of Hanoi game is very useful in understanding the recurrence relation. The recurrence relation is a mathematical formula that define a sequence.

Each term of the sequence is found by applying the formula to one or more previous terms. It also requires initial values to start the sequence.

Let’s understand the working of Tower of Hanoi which is a recurrence relation.

The Rules for Tower of Hanoi

It is a game of moving N disk between 3 needles. However, there are some rules we must follow before moving a disk from one needle to second needle.

Rule 1: Move only one disk at a time and it must be a top one.

Rule 2. Cannot move a larger disk on top of smaller one.

Rule 3: Number of moves should be minimum.

Let see how this works for 3 disk Tower of Hanoi game and using output of the game we can find solution to Tower of Hanoi game for N disk.

Figure 1 - Tower of Hanoi - Initial Setup with Needles
Figure 1 – Tower of Hanoi – Initial Setup with Needles

Initially , our disks stacked in needle 1 and other two remain empty. Each time we move a disk it is counted as 1.

Figure 2 - Disk Move From Needle 1 to Needle 3
Figure 2 – Disk Move From Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

Figure 3 - Move disk from Needle 1 to Needle 2
Figure 3 – Move disk from Needle 1 to Needle 2

Move top disk from needle 1 to needle 2.

Figure4 - Move disk from Needle 3 to Needle 2
Figure 4 – Move disk from Needle 3 to Needle 2

Move top disk from needle 3 to needle 2.

Figure 5 - Move largest disk from Needle 1 to Needle 3
Figure 5 – Move largest disk from Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

Figure 6 - Move disk from Needle 2 to Needle 1
Figure 6 – Move disk from Needle 2 to Needle 1

Move top disk from needle 2 to needle 1.

Figure 7 - Move disk from Needle 2 to Needle 3
Figure 7 – Move disk from Needle 2 to Needle 3

Move top disk from needle 2 to needle 3.

Figure 8 - Move final disk from Needle 1 to Needle 3
Figure 8 – Move final disk from Needle 1 to Needle 3

Move top disk from needle 1 to needle 3.

It took total 7 moves to shift all 3 disks to the destination(Needle 3).

Computing for 4 Disk Tower of Hanoi Game

Let the total number of disk move be H.
If we want to compute total count for 4 disk Tower of Hanoi game.

H_{n} = 2(H_{n-1})+1\\
= 2 (7 ) + 1\\
= 14 + 1
= 15 \hspace{3px} moves

There minimum 15 disk move required for 4 disk Tower of Hanoi game.

We can derive a much easier formula for  H_{n}=2(H_{n-1}) +1

H_n = 2^n - 1

How we arrived at this solution, we leave it as an exercise for you.