The Tower of Hanoi is a classic project assignment that most student of Computer Science would encounter in their academic classes.
It is usually used to illustrate the power of recursive logic in a program, of cause that it is also a great puzzle to give some good exercise to our brain.
So what is the problem we are trying to solve?
The giving:
It consists of three rods, and a number of discs of different sizes (but no two discs with the same size). The disc has hole in the middle and can be moved from one rod to another. The puzzle starts with the discs in a neat stack in ascending order of size on any one rod, meaning the smallest disc at the top.
The goal:
Move the entire stack to another rod. Now you must follow the list of rules below. Don’t do what I did to produce the image, I cheated by just rotating the image 🙂
The rules:
- You can only move 1 disc at a time
- You can only move the top disc on a stack
- You can not place a larger disc on top of a smaller disc.
Solution in Java using recursion:
Please note the simplicity of this program. I added some tracing code to help the reader to follow it, otherwise, the actual processing code should be 1/2 the size.
Here is the output from the program
Let’s discuss it: this is an amazing example on how elegant a recursive solution is. Only certain problem would lend itself to the benefit of recursion. They exhibit recursive behavior by two properties:
- A base case with a terminating condition that will produce a result without the recursion.
- A set of rules that reduce all other cases toward the base case.
Recursion occurs when a big problem can be broken down into smaller problems that are the same. All problem can be solved with the same solution, and end with a final stopping condition.
In the case of Tower of Hanoi, the big problem is that we need to move n discs from the first rod to the third rod. But you can also generalize it as move n disc from a start rod to and end rod, and you can use a intermediate rod to assist you. Now the big problem is “move n disc from a start rod to and end rod, and you can use an intermediate rod to assist you.
The smaller problem is “first move n-1 discs from a start rod to the intermediate rod”, and the stopping condition is now you can move the #n disc from the start rod to the end rod.
And this is your recursion, it is important to note each rod plays a different role in each recursion. If you repeat this processing for n, n-1, n-2, …, 1 disc. You will have moved all n discs from the first rod to the third rod.
This is what you see in the process function, these few lines of code is the recursion logic, and don’t worry if you need to analyze this a bit, as the code is very simple but also very powerful!
In case if you are interested, I have the Java code in my Github repository.
Please feel free to download and play with this in one of you favorite IDE. Have fun!