We will learn what recursion is and why it can help simplify your code.
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.
Given the Fibonacci number defined as
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.
The Tower of Hanoi is an amazing mathematical problem to solve.
Before we set the rules, let’s see how our universe looks like.
We need to represent the towers. This can be done by using a list of list (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.
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)
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.
See the full FREE course page here.
If you’re serious about learning Python, there’s nothing better than strong commits. At your request, we have created an improved version of this popular free online course.
This version has the following benefits to enhance your learning journey.
Start the change in your life and commit to doing something amazing that you have always dreamed of.
Sign up and become part of the exclusive Python Like a Pro elite.
Why learn Python? There are many reasons to learn Python, and that is the power…
What will you learn? How to use the modulo operator to check if a number…
There are a lot of Myths out there There are lot of Myths about being…
To be honest, I am not really a great programmer - that is not what…
What does it take to become a Data Scientist? Data Science is in a cross…
What will you learn? Need to setup a SQL server? You don’t need to install…