How To Solve Tower of Hanoi with Recursion

What will we cover in this tutorial?

We will first explain and understand Tower of Hanoi programming challenge. It is one of those programming challenges that are highly liked among programmers.

• Understanding the problem is easy.
• Solving it seems difficult.
• Using recursion makes it easy and elegant to solve.

You should be one of those that masters the Tower of Hanoi.

Step 1: Understand the Tower of Hanoi challenge

Tower of Hanoi is a mathematical game, which has three rules. Before we set the rules, let’s see how our universe looks like.

The disk all have different sizes as pictured above.

The goal is to move all the disks from on tower (rod) to another one with the following 3 rules.

1. You can only move one disk at the time.
2. You can only take the top disk and place on top of another tower (rod).
3. You cannot place a bigger disk on top of a smaller disk.

The first two rules combined means that you can only take one top disk and move it.

Say, in the above we have moved the disk 1 from the first to the second tower (rod).

After that move, we can move disk 2 or disk 1.

The third rule says, that we cannot move disk 2 on top of disk 1.

Those are the 3 rules of the game.

Now do yourself a favor and try to think how you would solve that. How do you get from here.

To here following the 3 rules.

Step 2: Recall recursion and unleash the power of it

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

https://en.wikipedia.org/wiki/Recursion_(computer_science)

While that is a beautiful and perfect definition – there is still need to exemplify what that means.

A simple example is to sum up the numbers from 1 to n.

It can be a bit difficult to connect the definition of recursions to getting the sum of the integers 1 + 2+ 3 + … + (n – 1) + n.

Let’s first try to do in the iterative way.

def summation(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum
print(summation(10))

While there is thing wrong with the above solution, you can turn that into a recursive function by the following.

def summation(n):
    if n == 0:
        return 0
    return n + summation(n - 1)
print(summation(10))

As you see, the problem of summing the numbers from 1 to n, is actually reversed to sum the numbers n, n – 1, n – 2, …, 1. You also notice, that it is true that the summation(n) is equal to n + summation(n – 1).

Wow, that was it. We are breaking the problem down to a problem of smaller size. Just like the definition said.

Also, notice the importance to have a base case in the function. In the above we choose for n == 0 to return 0. This ensures that the recursive calls to not continue forever (or when the Python interpreters stops due to maximum recursion depth).

Try it.

def summation(n):
    return n + summation(n - 1)
print(summation(10))

Well, what did we gain from making the function recursive?

Good question. The above might not be a good example of how recursion helps you. The example of Tower of Hanoi will show you the benefit. It will make your code easy and straight forward.

Step 3: Implement Tower of Hanoi with a recursive function

Now we need to think recursive. Consider the problem again.

How can we break that down to a smaller problem?

Think backwards. Just like the summation from Step 2. What do we need to make happen if we should move disk 3 from first tower (rod) to the last tower (rod)?

Exactly. Then we can move disk 3 to the final destination.

And after that, we should move the smaller problem of the 2 disks on top fo disk 3.

Wow. That is the formula. It is all you need to know.

1. Move the smaller problem of 2 disks from first tower (rod) to second tower (rod).
2. Move the big disk from first tower (rod) to last tower (rod).
3. Move the smaller problem of 2 disks from second tower (rod) to last tower (rod).

Now we need to generalize that.

First understand that there can be any number of disks in an instance of Tower of Hanoi. This means that the problem starts with n disks. If we number the towers (rods) 0, 1, and 2.

Then we have that all n disks start on tower (rod) 0 and should end in tower (rod) 2.

Now we can break down the problem to the following. Given n disks that needs to be moved from start_tower to dest_tower (destination), using aux_tower (auxiliary).

1. Move subproblem of n – 1 disks from start_tower to aux_tower.
2. Move disk n to dest_tower.
3. Move subproblem of n – 1 disk from aux_tower to dest_tower.

See the code below.

class Towers:
    def __init__(self, disks=3):
        self.disks = disks
        self.towers = [[]]*3
        self.towers[0] = [i for i in range(self.disks, 0, -1)]
        self.towers[1] = []
        self.towers[2] = []
    def __str__(self):
        output = ""
        for i in range(self.disks, -1, -1):
            for j in range(3):
                if len(self.towers[j]) > i:
                    output += " " + str(self.towers[j][i])
                else:
                    output += "  "
            output += "\n"
        return output + "-------"
    def move(self, from_tower, dest_tower):
        disk = self.towers[from_tower].pop()
        self.towers[dest_tower].append(disk)

def solve_tower_of_hanoi(towers, n, start_tower, dest_tower, aux_tower):
    # Base case - do nothing
    if n == 0:
        return
    # Move subproblem of n - 1 disks from start_tower to aux_tower.
    solve_tower_of_hanoi(towers, n - 1, start_tower, aux_tower, dest_tower)
    # Move disk n to dest_tower.
    towers.move(start_tower, dest_tower)
    print(towers)
    # Move subproblem of n - 1 disk from aux_tower to dest_tower.
    solve_tower_of_hanoi(towers, n - 1, aux_tower, dest_tower, start_tower)

t = Towers()
print(t)
solve_tower_of_hanoi(t, len(t.towers), 0, 2, 1)

The code includes a simple print function to see the trace of the movings.

Too fast?

Now this often seems a bit too fast. Didn’t we leave out all the subproblems?

That is the beauty of it. We actually didn’t

You tell the machine how to solve the problem using a smaller instance of the problem. This was done with the three things we did. First, move the subproblem away. Second, move the the biggest disk. Finally, move the subproblem on top of biggest disk.

How does that solve it all. See, you solve it for general n, hence, the smaller subproblems solves it by the same formula and we ensure the base case when there are no disks to move.

Python for Finance: Unlock Financial Freedom and Build Your Dream Life

Discover the key to financial freedom and secure your dream life with Python for Finance!

Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.

Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.

Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.

Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!

Python for Finance a 21 hours course that teaches investing with Python.

Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.

“Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.