Introduction to Python Programming. Section 17. Recursion
17 Recursion
17.1 Objectives
In this section we will show you:
- That recursion is a concept that extends way beyond computer programming.
- How to recognize whether or not a task is suitable for recursion.
- How to implement recursion correctly.
- What can happen if recursion is not done right.
17.2 Why learn about recursion?
"To iterate is human, to recurse divine." (L. Peter Deutsch)
This classical programming quote is 100% true - recursion is a beautiful and powerful tool. On the other hand, it is important to know that as any other tool, it is suitable for some tasks but not for all.
17.3 Introduction
Many websites describe recursion more or less as follows:
- "Programming technique where a function can call itself..."
- "The process in which a function calls itself..."
But recursion is much more. It can be found in many areas ranging from art and linguistics to mathematics and computer science. The following image shows an example of recursion in art: – the so-called Russian dolls.
Notice that they are all very similar, almost identical, just getting smaller and smaller. In fact, they can be inserted in each other so that at the end the largest one contains all of them.
17.4 Is your task suitable for recursion?
Let’s talk about using recursion to solve certain tasks. An important skill that you need to acquire is to recognize whether a task is suitable for recursion or not. All tasks which are suitable for recursion are similar:
- Part of the task can be solved by any method.
- The rest leads to exactly the same task, just smaller.
- Typically, recursive tasks are repetitive in nature.
Let’s show a few examples.
Example 1: Eating your lunch is recursion
Imagine that your "task" is to eat your food. If you don’t like chili, picture your favorite
food now. How do you eat it? Well, first you check: Is there any more left? If so, you eat a bite.
Then there is a bit less food to eat. But you can start the original task again: Eat your
food!
Example 2: Cleaning up is recursion
Your next task is to put all the Lego pieces back into the box. First you check the floor: Are
there some pieces still lying around? If so, collect a few and put them into the box. Then there
are fewer loose pieces on the floor. So your can start the original task again: Put all the Lego
pieces back into the box!
Example 3: Reading a book is recursion
The third and last example is about reading a book. Your progress will be measured by the number of unread pages. First you check: Are there any more pages left to read? If so, read a few pages from where you left off. After that, fewer pages remain, so your task got smaller. But it is still the same: Read the rest of the book!
17.5 Calculating the factorial
The factorial n! of a positive integer n is the product n ⋅ (n - 1) ⋅ (n - 2)…2 ⋅ 1, and moreover
the factorial 0! is 1. This is a perfect task for recursion because n! is n ⋅ (n - 1)! which means
that the task can easily be reduced to the same task, just smaller. Here is the corresponding
Python code, with a sample calculation of 5! at the end:
On line 3, the function factorial calls itself – this is the recursive call. For every recursive call, a new copy of the function is created in computer memory.
The program looks extremely simple, but there is one important thing which is easy to miss – notice that the recursive call is made from the body of a stopping condition. Every recursive algorithm needs a stopping condition. Without one, it instantly turns into an infinite loop. In fact, obtaining an infinite loop is the most frequent bug in the design of recursive algorithms. We will talk about it in more detail in the next subsection.
But before we get there, let’s take a closer look at the previous program. In order to gain
more insight into what is happening inside, we will add some debugging prints into it. First
let’s run the program, and then we will discuss the output:
if n > 0:
print(~Calling factorial(~ + str(n-1) + ~)~)
fact = factorial(n-1)
print(~Obtained factorial(~ + str(n-1) \
+ ~) which is ~ + str(fact))
print(~Returning ~ + str(n) + ~ * factorial(~ \
+ str(n-1) + ~) which is ~ + str(n*fact))
return n * fact
print(~Recursion finished.~)
return 1
print(factorial(5))
Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
Calling factorial(0)
Recursion finished.
Obtained factorial(0) which is 1
Returning 1 * factorial(0) which is 1
Obtained factorial(1) which is 1
Returning 2 * factorial(1) which is 2
Obtained factorial(2) which is 2
Returning 3 * factorial(2) which is 6
Obtained factorial(3) which is 6
Returning 4 * factorial(3) which is 24
Obtained factorial(4) which is 24
Returning 5 * factorial(4) which is 120
120
The first call to the function occurs on the last line of the program as factorial(5). With n = 5 the condition on line 2 is satisfied, and therefore the function calls itself on line 4 as factorial(4).
At this moment, a new copy of the function is created in computer memory and the value of n is 4. Then again, the condition on line 2 (of the copy) is satisfied, and the function calls itself on line 4 as factorial(3).
At this moment, a new copy of the function is created in computer memory and the value of n is 3. This goes on until a new copy of the function is created and the value of n is 0.
This is a very important moment because the condition on line 2 is not satisfied. Hence the fifth recursive copy of the function displays ~Recursion finished~, returns 1, and ends.
At this moment, we are back on line 4 of the fourth recursive copy of the function, with fact = 1. The rest of the body of the condition is executed, and because fact = 1 and n = 1, the return statement returns 1. Then the fourth recursive copy of the function ends.
At this moment, we are back on line 4 of the third recursive copy of the function, with fact = 1. The rest of the body of the condition is completed, and because fact = 1 and n = 2, the return statement returns 2. Then the third recursive copy of the function ends.
This goes on until also the second and first recursive copies of the function are finished, and finally, also the main call to the function on the last line of the program ends.
17.6 Stopping condition and infinite loops
To illustrate the importance of the stopping condition, let us remove it from the previous
program:
print(~Calling factorial(~ + str(n-1) + ~)~)
fact = factorial(n-1)
print(~Obtained factorial(~ + str(n-1) \
+ ~) which is ~ + str(fact))
print(~Returning ~ + str(n) + ~ * factorial(~ \
+ str(n-1) + ~) which is ~ + str(n*fact))
return n * fact
print(~Recursion finished.~)
return 1
print(factorial(5))
Then, a new copy of the function is automatically created on line 3, which means an infinite
loop. Here is the corresponding output
Python then throws a RecursionError:
File ~<string>~, line 10, in <module>
File ~<nclab>~, line 3, in factorial
File ~<nclab>~, line 3, in factorial
File ~<nclab>~, line 3, in factorial
[Previous line repeated 987 more times]
File ~<nclab>~, line 2, in factorial
RecursionError: maximum recursion depth exceeded while
getting the str of an object
17.7 Parsing binary trees
Unfortunately, most examples which are used to explain recursion are so simple that
they can be solved more naturally without recursion. For example, the factorial
from the previous subsection can be calculated non-recursively using a simple for
loop:
The beauty and power of recursion shows itself in more advanced applications. One of such applications are binary trees.
A binary tree "grows" from the top down. The circles are called nodes. Each node contains a number, and it can have up to two branches (hence the name binary tree). The number of levels in called depth – the sample binary tree in Fig. 78 has depth 4. Usually, the shape and depth of the binary tree are unknown.
One way to represent such a binary tree in Python is using embedded lists. Each node is a three-item list where the first item is the number, the second item is the left branch, and the third item is the right branch. An empty list is used for an empty branch. Let’s show some examples.
In Fig. 78, the node with the number 2 is without branches, and therefore it is represented as [2, [], []]. The other nodes without branches just differ in the number. The node with the number 9 only has the left branch, and therefore it is represented by the list [9, [4, [], []], []]. The node with the number 6 has both branches, and therefore it has the form [6, [5, [], []], [11, [], []]]. The entire tree can then be written as [2, [7, [2, [], []], [6, [5, [], []], [11, [], []]]], [5, [], [9, [4, [], []], []]]].
Now imagine that our task is to parse such a binary tree and add all the numbers. This would be extremely difficult without recursion. On the other hand, a recursive algorithm is very simple:
- The list (let’s call it t) has three items t[0] (the number), t[1] (the list representing the left branch), and t[2] (the list representing the right branch).
- If t is empty, return 0.
- Otherwise add to the value t[0] all values in the left branch t[1] and all values in the right branch t[2], and return the result.
This is the corresponding code. Take a minute to verify that indeed all the values in the tree from
Fig. 78 add up to 51!
Table of Contents
- Preface
- 1. Introduction
- 2. Using Python as a Scientific Calculator
- 3. Drawing, Plotting, and Data Visualization with Matplotlib
- 4. Working with Text Strings
- 5. Variables and Types
- 6. Boolean Values, Functions, Expressions, and Variables
- 7. Lists, Tuples, Dictionaries, and Sets
- 8. Functions
- 9. The ’For’ Loop
- 10. Conditions
- 11. The ’While’ Loop
- 12. Exceptions
- 13. File Operations
- 14. Object-Oriented Programming I – Introduction
- 15. Object-Oriented Programming II – Class Inheritance
- 16. Object-Oriented Programming III – Advanced Aspects
- 17. Recursion
- 18. Decorators
- 19. Selected Advanced Topics