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

Learn Recursion with Python

We will learn what recursion is and why it can help simplify your code in Python to solve complex problems like Fibonacci and Tower of Hanoi.

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 into 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. If 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 (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 is 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 into smaller problems and send the problems to the next one. When you get the answer you update it with your part.

This is done all the 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 in Python

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 the 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, Fibonacci solved with recursion in Python.

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 what our universe looks like.

  • All the disks have different sizes.
  • The goal is to move all the disks from one tower (rod) to another one with the following 3 rules.
    1. You can only move one disk at a time.
    2. You can only take the top disk and place it on top of another tower (rod).
    3. You cannot place a bigger disk on top of a smaller disk.
  • The first two rules combined mean 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 – follow 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 disks at the same time
  • Then we can move disk 3 in place.
  • And we can move the subproblem of 2 disks in 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 lists (see more about lists).

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 (see more about for-loops).

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 the 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 the 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 an 8 hours FREE video course with full explanations, projects on each level, 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.
  • 2 FREE eBooks to support your Python learning.

See the full FREE course page here.

Learn Python

Learn Python A BEGINNERS GUIDE TO PYTHON

  • 70 pages to get you started on your journey to master Python.
  • How to install your setup with Anaconda.
  • Written description and introduction to all concepts.
  • Jupyter Notebooks prepared for 17 projects.

Python 101: A CRASH COURSE

  1. How to get started with this 8 hours Python 101: A CRASH COURSE.
  2. Best practices for learning Python.
  3. How to download the material to follow along and create projects.
  4. A chapter for each lesson with a descriptioncode snippets for easy reference, and links to a lesson video.

Expert Data Science Blueprint

Expert Data Science Blueprint

  • Master the Data Science Workflow for actionable data insights.
  • How to download the material to follow along and create projects.
  • A chapter to each lesson with a Description, Learning Objective, and link to the lesson video.

Machine Learning

Machine Learning – The Simple Path to Mastery

  • How to get started with Machine Learning.
  • How to download the material to follow along and make the projects.
  • One chapter for each lesson with a Description, Learning Objectives, and link to the lesson video.

Leave a Comment