Recursion is ubiquitous in the programming world. In its simplest form, recursion is when a function calls itself from within its own code. When I was just starting out as a programmer, I found recursion rather difficult to understand. I kept wondering “Why on earth would we need to write a function that calls itself?”. The answer became a lot clearer when I started working through some examples.
This is what we will accomplish together in this story! We will learn recursion by looking at simple examples that demonstrate the usefulness of this programming technique. While it might seem odd to you at first that a function calls itself, it turns out this kind of programming technique appears everywhere in the real world.
There are a few crucial things to keep in mind when it comes to recursion. For one, a recursive function must actually terminate and return at some point. This is called the breaking condition. This prevents infinite loops from happening and the program from crashing so that the computer does not run out of memory trying to keep track of all the function calls.
Each time the function is called, the values of the arguments of the previous calls are stored aside instead of being overwritten by the new call. This is accomplished by what is called a “call stack” which, as the name suggests, is implemented through the stack data structure which we saw in my previous story.
Python Data Structures: Your Starter Kit to Learning Algorithms
Arrays, Linked Lists, Stacks, Queues and Hash Tables.
Recursion at Work I: Building a Countdown Function
Let’s look at a common example of recursion by building a countdown function!
if x == 0:
For this to make more sense, let’s unpack what happens when the countdown function is called for x = 3. I tried explaining all the function calls in this colorful infographic below. I hope it helps!
Notice that as long as the breaking condition is not satisfied, the function keeps executing the else statement which prints the number and calls the function itself again for the number minus one. It’s only until call 4 that the breaking condition is satisfied and the function returns. Always keep in mind that the values of previous calls are stored aside and not overridden by the values of new calls.
Recursion at Work II: Building the Power Function
Recall that raising a number a to the power b means multiplying a by itself b-times. The special case for the power function is that anything to the power zero is equal to one. When building mathematical functions, it is always a good idea to think of special cases. These usually end up being the breaking condition for your recursion.
Let’s build the power function!
def power(a, b):
# taking care of special cases first
if b == 0:
return a * power(a, b-1)
Try unpacking the power function we defined above by explicitly writing out an infographic of each of the function calls for the following. Reference the infographic we created for countdown(3) if needed!
Note that the expression after the else statement above should make a lot of sense since a^b = a[a^(b-1)].
Recursion at Work III: Building the Factorial Function
Let’s start with a quick math recall! The factorial of a positive integer n (denoted by an exclamation mark ! after an integer) is simply defined as n(n-1)(n-2) … 1. For example, 4! = 4 x 3 x 2 x1.
The special case here is that 0! = 1. Again, like for the power function, this will be useful when we start setting up the breaking condition of our recursive function.
Now let’s build up our recursive factorial function!
# taking care of special cases first
if (num == 0):
return num * factorial(num-1)
Note that this makes a lot of sense since we can always rewrite n! as n(n-1)!
To get some more practice, try explicitly writing out all function calls until the function returns for:
Recursion is a very efficient programming technique if used in the right place and at the right time. Recursion is when a function calls itself inside itself. What you always need to remember is that any recursive function you write must have a breaking condition so that your program does not crash by entering into infinite loops of calling itself again.
Recursive functions store the values of the arguments of each recall aside instead of overriding the values upon each consecutive recall. This is stored using what’s called as the “call stack”.
I hope this helped introduce you to recursion or helped you understand it a lot better using unpacked examples that showcase the usefulness of this programming technique.
Happy learning everyone!