Solve Tower of Hanoi using Recursion in C

Summary: In this tutorial, we will learn how to solve the Tower of Hanoi problem using recursion in C programming language.

What is the Tower of Hanoi?

Tower of Hanoi is a game where a certain number of disks of different sizes on a particular rod have to be transferred to the final rod with the help of other available rods following the following rules:

1. One disk can be transferred at a time.
2. A large disk cannot be placed on a small disk.

Following is the initial condition of the Tower of Hanoi:

Following is the final solution of the Tower of Hanoi:

Tower of Hanoi Solution using Recursion

To solve the Tower of Hanoi using Recursion, we need to understand a little trick and the concept of Recursion.

Suppose we are given 3 (n) disk as stated in the first diagram and asked to solve this using recursion. And we also know that putting a large disk over small ones is not allowed.

The trick is to assume that we are given only two disks (as stated in the picture).

Now we need to shift the upper disk i.e n-1 (which actually contains 2 Disk in the current scenario) to B so that we can shift the last disk (n-th) to C.

The main point is we will not do this. The recursive function will take the responsibility to shift n-1 disks (2 disks in this case) to B.

hanoi(n-1,rodFrom,rodTo,rodMiddle);

where rodFrom = A , rodTo = B and rodMiddle = C will be used as auxiliary rod by the recursive function.

Now we need to shift the last disk (nth or largest disk) to rod C. So we will do this Just by outputting the statement.

printf("Disk %d moved from %c to %c \n",n,rodFrom,rodTo);

where n=3, rodFrom = A and rodTo = C .

Now again the n-1 disk (2 disks) in rod B need to be shifted to C with the help of rod A. Since there are multiple disk i.e n-1, so let the recursive function handle this task.

hanoi(n-1,rodMiddle,rodFrom,rodTo);

where rodFrom = B , rodTo = C and rodMiddle = A will be used as auxiliary rod by the recursive function.

Finally, the Tower of Hanoi is solved.

Here, is the implementation of the solution in C:

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    hanoi(3, 'A', 'B', 'C');
    return 0;
}
 
void hanoi(int n, char rodFrom, char rodMiddle, char rodTo){
    if(n==1){
        printf("Disk 1 moved from %c to %c \n",rodFrom,rodTo);
        return;
    }
    hanoi(n-1,rodFrom,rodTo,rodMiddle);
    printf("Disk %d moved from %c to %c \n",n,rodFrom,rodTo);
    hanoi(n-1,rodMiddle,rodFrom,rodTo);
 
}

Output:

We have shown you the solution of 3 disk’s Tower of Hanoi problem in C.

The above program can be used to solve any number of Disks in the Tower of Hanoi game i.e any value of n. If you have doubts then comment below.