C Program for Tower of Hanoi
FREE
Overview
Tower of Hanoi is a purely mathematics-based puzzle game that consists of three rods with a number of disks of varying diameters arranged in ascending order of diameter from the top, thus forming a conical shape consisting of disks. The aim of the game is to move the stack of disks from the first rod to the last rod using an auxiliary rod by following certain rules. The rules of the game are as follows:
- One disk can be moved only once at a time.
- Upper disk can be moved from one of the stacks and placed on top of another empty rod.
- Disk of the largest diameter can't be placed on a disk of the smaller diameter.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Introduction to Tower of Hanoi in C
To solve the Tower of Hanoi Program in C programming language, the most basic implementation is by writing a program using
- Recursive Method
- Iterative method
C Program to Solve Tower of Hanoi Using Recursive Method
To solve the problem of the Tower of Hanoi in C, using the recursive method, We will consider the following:
Three rods A, B and C: where A is the rod from which the disks will be shifted. A acts as a source. B is the auxiliary rod using which the disks are moved to C. C is the destination rod.
Explanation
- Tower of Hanoi when only one disk and towers A, B, and C are given:
- Tower of Hanoi when 2 disks are given with towers A, B, and C:
- Tower of Hanoi when 3 disks are provided with rods A,B, and C:
Similarly.
- Tower of Hanoi when n disks are given with rods A, B, and C
Note: For 'n' disks number of moves= .
Let's look into the implementation of the following program using the C programming language.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreExample
Output:
C Program to Solve Tower of Hanoi Using Iterative Method
Here also we'll consider 3 rods A, B and C as the source rod, auxiliary rod and destination rod.
Turn Learning into Career Growth
Explanation
When i=1, we will shift the disk from source to destination.
When i=2, the auxiliary rod is empty so we move the disk from the source rod to the auxiliary rod.
When i=3, we need to shift the remaining disk to the destination rod and for it, we will shift the disk from destination to auxiliary.
In a similar way, we observe a pattern here, ie., after 3 subsequent moves, the destination rod becomes acceptable to get a disk(That's the reason we use i%3).
Example
Output:
Complexity of Tower of Hanoi in C
Time complexity of Tower of Hanoi using the
iterative method:
Space complexity:
Time complexity of Tower of Hanoi using
Recursive method:
Space complexity:
Ready to conquer complex algorithms? Our Dynamic Programming Certification course is your ticket to success. Enroll today and elevate your coding proficiency!
Conclusion
- We learned two approaches to solving the Tower of Hanoi program in C programming language: The iterative method and the Recursive method.
- Three rods are considered as a source, destination, and auxiliary rods for transferring the disks.
- The number of moves required for 'n' disks is .
- Time complexity of the Tower of Hanoi program in C using the iterative method is O(n) and using the recursive method is .
- Space complexity for both auxiliary and iterative approaches for solving the Tower of Hanoi program in c is O(n).
