Master Recursion with Python with Examples | Fibonacci numbers | Tower of Hanoi

What will we cover?

We will learn what recursion is and why it can help simplify your code.

Step 1: What is recursion?

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

It is often used in computer science to take one complex problem and break it down to smaller sub-problems, which eventually will have a simple base case.

How could a real life problem be?

Imagine you are standing in a long line and you do not see the beginning of it. You want to figure out how many people are in front of you.

How can you solve this?

Ask the person in front of you how many people are in front. It the person does not know, then this person should ask the person in front as well. When you get the answer, return the answer added one (as that person will count one).

Imagine this goes on until you reach the first person in the line. Then this person will answer 0 (there are no-one in front).

Then the next person will answer 1. The next 2 and so forth.

When the answer reaches you, you get the answer of how many are in front of you.

What to learn from this?

Well, the problem of how many are in front of you is complex and you cannot solve it yourself. Then you break it down to a smaller problem, and send that problem to the next one. When you get the answer you update it with your part.

This is done all they way down to the base case when it reaches the first person.

This is the essence of recursion.

Step 2: The first recursion problem you solve: Fibonacci numbers

Given the Fibonacci number defined as

  • F_0 = 0
  • F_1 = 1
  • F_n = F_(n-1) + F_(n-2)

The sequence begins as follows

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Create a list of first n Fibonacci numbers.

First take a moment and try to think how you would solve this? Seems a bit complex.

Then look at this recursive solution.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

It is important to notice the base case (n <= 1). Why? Because without the base case it would never terminate.

Then notice how it makes calls to smaller instances of the same function – these are the recursive calls.

Now that is beautiful.

Step 3: Tower of Hanoi

The Tower of Hanoi is an amazing mathematical problem to solve.

Tower of Hanoi Explained

Before we set the rules, let’s see how our universe looks like.

  • All the disks have different sizes.
  • 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.
  • The third rule says, that we cannot move disk 2 on top of disk 1.
  • Game: How do you get from here.
  • To here – following the 3 rules.

How to Solve Tower of Hanoi Recursively

  • Assume you can solve the smaller problem of 2 disks.
  • Then we can move 2 disk at the same time
  • Then we can move disk 3 on place.
  • And we can move the subproblem of 2 disk on place.

The Implemented Solution of Tower of Hanoi in Python

We need to represent the towers. This can be done by using a list of list.

towers = [[3, 2, 1], [], []]

Then a way to move plates.

def move(towers, from_tower, dest_tower):
    disk = towers[from_tower].pop()
    towers[dest_tower].append(disk)
    return towers

As a helper function we want to print it on the way.

def print_towers(towers):
    for i in range(3, 0, -1):
        for tower in towers:
            if len(tower) >= i:
                print(tower[i - 1], end='  ')
            else:
                print('|', end='  ')
        print()
    print('-------')

Then print_towers(towers) would print

1  |  |  
2  |  |  
3  |  |  
-------

Finally, the algorithm we want to implement is as follows.

  • Step 1: Represent the towers as [[3, 2, 1], [], []]
  • Step 2: Create a move function, which takes the towers and can move a disk from one tower to another.
    • HINT: Use .pop() and .append(.)
  • Step 3: Make a helper function to print the towers
    • HINT: Assume that we have 3 towers and 3 disks
  • Step 4: The recursive function
    • solve_tower_of_hanoi(towers, n, start_tower, dest_tower, aux_tower)
    • n is the number of disks we move, starting with 3, then we call recursive down with 2, 1, and 0.
    • The base case is n = 0, just return in that case
    • Move subproblem of n – 1 disks from start_tower to aux_tower.
    • Move disk n to dest_tower. (you can print the tower here if you like)
    • Move subproblem of n – 1 disk from aux_tower to dest_tower.
def solve_tower_of_hanoi(towers, n, start_tower, dest_tower, aux_tower):
    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. (you can print the tower here if you like)
    move(towers, start_tower, dest_tower)
    print_towers(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)

Try it out.

towers = [[3, 2, 1], [], []]
print_towers(towers)
solve_tower_of_hanoi(towers, 3, 0, 2, 1)

Want more?

I am happy you asked.

If this is something you like and you want to get started with Python, then this is part of a 8 hours FREE video course with full explanations, projects on each levels, and guided solutions.

The course is structured with the following resources to improve your learning experience.

  • 17 video lessons teaching you everything you need to know to get started with Python.
  • 34 Jupyter Notebooks with lesson code and projects.
  • A FREE 70+ pages eBook with all the learnings from the lessons.

See the full FREE course page here.

Leave a Reply