Towers of Hanoi in Python using Recursion — Explained

Towers of Hanoi, the most common example taken when we speak about the term “Recursion”. Let’s discuss this problem in-depth and try to understand the recursion concept clearly.

Problem Statement:

Towers of Hanoi consists of three rods and n number of disks of different sizes, which can be moved to any rod. The puzzle starts with the disks on the initial rod in a neat stack in ascending order of size(smallest at the top).

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.

The minimal number of moves to solve this problem is (2^n)-1.

For example, if we have 3 disks, then the minimal number of steps would be 7.

Solution:

Let us use python to solve the problem recursively.

Starting the solution, we need to move a disc from one rod to another. So, let's define a function that does the job for us.

def move_disc(ffrom , to):
 print (“Move disc from {} to {}”.format(ffrom, to))

Okay that's not a spelling mistake of ‘from’, from is a keyword already so cannot use it as a variable. So, in the above function, we take two variables from and to which holds the initial and destination from where the disc is to be moved.

Now, let’s look at how we use recursion to solve this Towers of Hanoi problem.

Let’s assume the 3 rods as A, B, C, and 4 discs.

So here's the idea, if we want to move 4 discs from A to C using B, then we have to move the upper 3 discs to B using C first.

Then, we can move the last disc to c comfortably.

Now, we will move the remaining 3 discs from B to C using A. Done!!! It's simple. Here the problem is simplified from solving for 4 discs to solving for 3 discs, for 3 discs we solve it for 2 discs, and so on… If we want to do it for n discs, it's enough to solve for n-1 discs. This is the beauty of recursion.

Let's do the same in the form of code. Let's define a function towers_of_hanoi with 4 parameters, n(number of discs), from(from which rod we move the disc), via(which rod we use as via), and to(the destination rod).

def towers_of_hanoi(n, ffrom, via, to):
 if(n==0):
     return
 towers_of_hanoi(n-1, ffrom, via, to)
 move(ffrom,to)
 towers_of_hanoi(n-1, via, ffrom, to)

The base case “n==0” will be very important as the function keeps on calling itself an infinite number of times and it makes no sense. We keep on moving an n-1 number of discs to another rod (via) until we reach zero.

The output for the following shows the procedure to solve the problem and as discussed we get (2^n)-1 steps to solve it. The solution would go this way.

Move A to C
Move A to C
Move B to C
Move A to C
Move B to C
Move B to C
Move A to C
Move A to C
Move B to C
Move B to C
Move A to C
Move B to C
Move A to C
Move A to C
Move B to C

Here recursion comes into the picture even if the problem can be solved in the iterative method because the iterative way here can be way too complex. We solved it in just 4–5 lines using recursion. It takes a lot of practice to think recursively even if it looks simple. So keep on practicing.

HAPPY CODING!!!