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.
- 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.
An Example of a Recursive Algorithm in Python
To understand what recursion is, it’s probably best to look at an example first and then break it down to explain what is happening. Type this code into a new Python file.
if n <= 0:
countdown(n - 1)countdown(10)
Here’s the output:
What is going on here? Even though it’s a simple program, it contains the fundamental ingredients of recursion, sometimes known as “the Three Laws of Recursion.”
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. In the example above, 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 in the example above 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
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
if n == 1:
return n * factorial(n-1)print(factorial(5))
Here’s what happens before the final value of
120 is returned and printed:
| |-- factorial(4)
| | |-- factorial(3)
| | | |-- factorial(2)
| | | | |-- factorial(1)
| | | | | |-- return 1
| | | | |-- return 2
| | | |-- return 6
| | |-- return 24
| |-- return 120
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
| |-- countdown(4)
| | |-- countdown(3)
| | | |-- countdown(2)
| | | | |-- countdown(1)
| | | | | |-- countdown(0)
| | | | | | |-- return None
| | | | | |-- return None
| | | | |-- return None
| | | |-- return None
| | |-- return None
| |-- return None
How to Master Recursion in Python
Just released on LinkedIn Learning — my Python Recursion Video Course. Take a deep dive into the concepts, techniques, and applications of recursion using Python in this fun and accessible course: Python Recursion Video Course
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!
Originally published at https://compucademy.net.