Machine Learning
Data Structures
Algorithms
Problem Solving
Home >
Algorithms >
Tower of Hanoi – Recursion
Post author: Mrinal Pradhan
Post published: March 10, 2021
Post category: Algorithms / Problem Solving
Post comments: 0 Comments
The Tower of Hanoi is a mathematical game or puzzle. The puzzle was invented by the French mathematician Édouard Lucas in 1883. Numerous myths regarding the ancient and mystical nature of the puzzle popped up almost immediately.
The puzzle consists of three rods(or sticks) and N discs of distinct sizes. At the start of the game, all of the discs are stacked on one of the rods in a way that the size of the discs increase as we move down the rod. The objective of the problem is to move the entire stack of discs to another rod by taking the help of a third (or auxiliary) rod in minimum number of moves.
The rules to be obeyed while doing so are:
A larger disc cannot be placed over a smaller disc.
One move consists of moving one disc from one rod to another.
Here, we see we have 3(three) discs stacked on rod A which is the source rod. The stack is to be moved to the rod C which is the destination rod using rod B which is the auxiliary rod.
At first, the disc 1 is the only disc that can be moved, so we move it to the rod C.
Now, we can move two discs, but moving disc 1 back to rod 1 takes us back to the previous state and moving disc 1 to rod B may give the solution but not in minimum possible steps. Therefore, we move disc 2 to rod B.
The largest disc, disc 3 can be moved now but the rod C, the destination rod, has disc 1. So, to free rod C we move disc 1 to rod B.
Next move simply involves moving disc 3 to rod C.
To free the second- largest disc, disc 2 we move disc 1 to rod A.
Disc 2 is moved from rod B to rod C.
Finally, the last step is to move the smallest disc, disc 1 to rod C and completing the stack on the destination rod.
To solve this problem of the Tower of Hanoi, we use recursion. The basic idea behind the algorithm is to recursively place ‘n-1’ discs on the auxiliary rod then move the largest remaining disc to the destination rod and then finally moving the ‘n-1’ discs to the destination rod.
We can implement the recursive algorithm discussed above in C++ as follows:
Output:
Time Complexity: The total number of steps to solve the problem is 2 n -1. So the time complexity of the program is O(2 n ).
Space Complexity: The space complexity of the code is linear, that is, O(n).
https://en.wikipedia.org/wiki/Tower_of_Hanoi
Hope you enjoyed this article. For more such amazing articles, check out helloml.org . If you want to improve this article or report something incorrect, please send a mail to [email protected] .
Any copyright/wrong information claims will be directed to the author/s.
I am a Computer Science Engineering Student who loves to code. I am mostly fascinated by various algorithms and problem solving techniques. I also love to talk about these stuff and help people learn new things.
Tweet
Telegram
Register
Lost your password?
The Mystery of Self-Driving Cars
Program to Calculate Binomial Coefficient
Introduction to Circle Sort
Implementing Autoencoders
Merge Sort with Linked Lists
Join our internship program to learn and grow. All with a passion for technology can join.