In this article we discuss recursion in Python programming. Recursion is a fundamental concept in Computer Science, and regardless of what your development goals are, it is good to have an understanding of at least the basics.
Topics covered:
- The basic concept of recursion
- What is a base case?
- Some examples of recursive algorithms
- Visualizing recursion
In terms of day-to-day development, the amount you use recursion will vary by context. Some developers may make little or no explicit use of it while for others it will be a mainstay. Regardless, recursion is part of the very fabric of computing, and even if you don’t use it explicitly in your everyday work, you can bet it’s happening a whole lot behind the scenes.
Here are some examples of where recursion is used in computing:
- traversing DOM elements
- processing recursively defined data such as that stored in trees
- command shells
- compilers and linkers
- evaluation of arithmetic expressions
- database systems
Recursion is so important and useful that almost all modern programming languages support it.
So what is recursion?
It’s probably best to look at an example first and then break it down to explain what is happening.
An Example of a Recursive Algorithm in Python
Type this code into a new Python file.
def countdown(n):
if n <= 0:
print("LIFTOFF!")
else:
print(n)
countdown(n - 1)
countdown(10)
Before you run it, have a think about what the output of this program might be. You can click below to see the solution.
What is going on here? Even though it’s a simple program, it contains the fundamental ingredients of recursion:
Base case
A base case is essential with recursion. Without it there is no way for the algorithm to “know” when to stop. Not having one is like having a while True loop – i.e. you get an infinite loop, except with recursion you will eventually hit your system’s maximum recursion limit. Here the base case is when n <= 0.
Movement toward the base case
The algorithm must approach the base case on each successive call, otherwise it can not terminate. Again comparing this to a while loop, not moving towards the base case is like not moving towards the condition for the while loop to exit. Each successive call here has n - 1 as its argument so we are approaching the base case. This is good.
A recursive call
The simple yet powerful idea here is that the function definition contains a call to itself within its body. Did you notice that the function definition for countdown() contains a call to the function countdown()?
Stages of recursion
One key thing to understand about recursion is that there are two stages to a recursive algorithm. Before anything is returned from the initial function call, all the subsequent recursive function calls are made, until the base case is reached. At that point, the call stack (which contains a frame for each function call), begins to unwind, until a value for the initial function call is returned.
This is probably best illustrated visually. Look at this representation of a call to the factorial(n) function, which calculates the product of decreasing values of n and whose mathematical symbol is !. For example 5! = 5 * 4 * 3 * 2 * 1
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
Here’s what happens before the final value of 120 is returned and printed:
|-- factorial(5)
| |-- factorial(4)
| | |-- factorial(3)
| | | |-- factorial(2)
| | | | |-- factorial(1)
| | | | | |-- return 1
| | | | |-- return 2
| | | |-- return 6
| | |-- return 24
| |-- return 120
120
>>>
factorial(5) calls factorial(4) which calls factorial(3) etc, until the base case is reached (n == 1), then each of the function calls returns its value, in the reverse order to that in which they were called, until the value for the initial call factorial(5) is returned.
We can use the same kind of diagram for our first example of a recursive algorithm, countdown(n) although is is less clear what is happening since nothing (actually None) is returned by each successive function call, as we are using print to output the value for each stage of the count.
|-- countdown(5)
5
| |-- countdown(4)
4
| | |-- countdown(3)
3
| | | |-- countdown(2)
2
| | | | |-- countdown(1)
1
| | | | | |-- countdown(0)
LIFTOFF!
| | | | | | |-- return None
| | | | | |-- return None
| | | | |-- return None
| | | |-- return None
| | |-- return None
| |-- return None
None
How to Master Recursion in Python
Learners often find recursion confusing when they first encounter it. This is completely normal. Recursion has the paradoxical quality of being both very simple and intuitive on the one hand, and seemingly confusing and complex on the other. The way to gain confidence and competence with the topic is by looking at lots of examples of recursive algorithms and, more importantly, writing them for yourself. You may also have to spend a bit of hard thinking time wrapping your head around what is happening. Having a whiteboard handy may help as you trace a particular function call and try to anticipate what happens next. Don’t be discouraged if it takes a while for your understanding of recursion to grow. It is well worth the effort!
Happy computing!