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.
In this tutorial, you will:
- Understand Recursion: Learn the concept of recursion and how it works in Python.
- Simplify Code Complexity: Explore how recursion can simplify your code by breaking down complex problems into smaller, more manageable subproblems.
- Solve Problems with Recursion: Apply recursion to solve specific problems, such as computing Fibonacci numbers and solving the Tower of Hanoi puzzle.
By the end of the tutorial, you will have a clear understanding of recursion and its benefits in simplifying code structure. You will also be equipped with the knowledge to apply recursion to solve complex problems efficiently in Python.
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.
- You can only move one disk at a time.
- You can only take the top disk and place it on top of another tower (rod).
- 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?
In the next lesson you will learn List and Dict Comprehension with Python
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.
- A FREE eBook to support your Python learning.
See the full FREE course page here.
Python Circle
Do you know what the 5 key success factors every programmer must have?
How is it possible that some people become programmer so fast?
While others struggle for years and still fail.
Not only do they learn python 10 times faster they solve complex problems with ease.
What separates them from the rest?
I identified these 5 success factors that every programmer must have to succeed:
- Collaboration: sharing your work with others and receiving help with any questions or challenges you may have.
- Networking: the ability to connect with the right people and leverage their knowledge, experience, and resources.
- Support: receive feedback on your work and ask questions without feeling intimidated or judged.
- Accountability: stay motivated and accountable to your learning goals by surrounding yourself with others who are also committed to learning Python.
- Feedback from the instructor: receiving feedback and support from an instructor with years of experience in the field.
I know how important these success factors are for growth and progress in mastering Python.
That is why I want to make them available to anyone struggling to learn or who just wants to improve faster.
With the Python Circle community, you can take advantage of 5 key success factors every programmer must have.
Be part of something bigger and join the Python Circle community.
