Tower Of Hanoi using Recursion in C

Let’s first understand what is the Tower of Hanoi problem.

What is the Tower of Hanoi Problem?

In this problem, we have given 3 towers. In one of the towers, there are a number of discs i.e., 3. Below is an example Image.



In our example, we have 3 towers – X, Y, Z, and 3 discs are present in X tower. The bigger disc is kept on the bottom of the tower and the smallest disc is kept on top of the tower. Now, the problem is we have to transfer all these discs from tower X to tower Z with the following conditions –We can move one disk at a time.
The larger disk should not be kept over the smaller disk.



We can’t keep a larger disc on a smaller disc. For moving the Discs from tower X to tower Z we required one more extra tower Y as an auxiliary tower. The following Images will help you to clearly understand this problem.



Step1. We have our 3 discs in tower X.



Step2. We have transferred our smaller disc from x to Z tower.




Step3. Now, we have transferred our second smaller disc from X to Y.



Step4. Now, we have transferred our smaller disc from Z to Y. (smaller disc on top of the second larger disc)



Step5. Now, we have transferred our larger disc from X to Z.





Step6. Now, we have transferred our smaller disc from Y to X.



Step7. Now, we have transferred our second larger disc from Y to Z.



Step 8. Finally, we have transferred our smaller disc from X to Z.




Now, we want our recursive function to work in the same manner, transfer discs by following the above conditions. So, let’s have a look at our recursive function which will do the same.


Tower of Hanoi Program using Recursion in C Language:

Let us first see the code and then we will understand the code using the tracing tree.

#include <stdio.h>

void TH(int num, int x, int y, int z)

{

    if(num > 0)

    {

        TH(num - 1, x, z, y);

        printf("From %d to %d \n", x, z);

        TH(num - 1, y, x, z);

        }

    }

int main()

{

    int numOfDisc = 3;

    int tower1 = 1, tower2 = 2, tower3 = 3;

    TH(numOfDisc, tower1, tower2, tower3);

}

Output: