Recursion in Python

What is recursion?

A recursive function is a self-referential function—that is, a function that references itself. Recursive functions have 3 main parts: a base case, a self-reference, and a counter that increments toward the base case. I think a recursive function is a lot like walking up and down a staircase.

The scene goes like this:

You are in your house at the top of the staircase and there is an item that you want at the bottom of the stairs. You walk down the stairs, one step at a time, until you reach the bottom of the staircase. At the bottom of the stairs, you pick up the item. Then walk up the stairs, again one step at a time, until you reach the top of the staircase.

So, in this simple example:

• The base case is the bottom of the stairs. When you get to the bottom of the stairs, you know you need to pick up the item and walk back up the stairs.
• The act of walking down the is the recursive function. You walk down the stairs, one step at a time, and you don’t stop walking until you are at the bottom of the staircase.
• The staircase is the counter. The count decreases or increases as you walk down or up the stairs, respectively.

So, that’s generally how recursion works.

Calculating Fibonacci numbers using recursion

The classic example used to explain recursion is calculating Fibonacci numbers.

As a brief refresher, the Fibonacci sequence starts with 1, 1. To find the next number, you add the two previous numbers together—so in this case, 1 + 1 = 2. So now our sequence looks like this: 1, 1, 2. To find the next number, you add the two previous numbers together—so 1 + 2 = 3. Now our sequence is 1, 1, 2, 3. And it continues like this: 1, 1, 2, 3, 5, 8, 13, 21, 34…

Fibonacci sequences are found all over the place, like in pinecones, in sunflowers, in music (like Debussy)—but that’s a bit outside the scope of this blog post.

The key to finding the value at a particular index in the Fibonacci sequence is to realize that you can calculate the value by working backwards. (This might be a good time to mention that Python uses zero-based numbering—in other words, counting starts at 0 and not at 1.)

For example, if you wanted to calculate the value of the number at index 6, you could “walk down the stairs”:

• The value at index 6 is equal to the value at index 5 plus the value at index 4.
• The value at index 5 is equal to the value at index 4 plus the value at index 3.
• The value at index 4 is equal to the value at index 3 plus the value at index 2.
• The value at index 3 is equal to the value at index 2 plus the value at index 1.
• The value at index 2 is equal to the value at index 1 plus the value at index 0.

But you know that the value at index 1 is 1 and the value at index 0 is also 1. So, you’ve reached the bottom of the stairs!

Now you can “walk back up the stairs”:

• You can calculate the value at index 2 because you know the value at index 0 is 1 and the value at index 1 is 1. So, 1 + 1 is 2.
• You can calculate the value at index 3 because you know the value at index 2 (which is 2) and the value at index 1 (which is 1). So, 2 + 1 is 3.
• You can calculate the value at index 4 because you know the value at index 2 (which is 2) and the value of index 3 (which is 3). So, 3 + 2 is 5.
• You can calculate the value at index 5 because you know the value at index 4 (which is 5) and the value at index 3 (which is 3). So, 5 + 3 is 8.
• Finally, you can calculate the value at index 6 because you know the value at index 5 (which is 8) and the value at index 4 (which is 5). So, 8 + 15 is 13.
• And 13 is the value that is returned!

Here’s what that looks like in Python:

This particular example happens to be a non-tail recursive function. You can tell that it is because there are multiple steps in the return—you need to calculate fibonacci_non_tail_recursion(end-1), calculate fibonacci_non_tail_recursion(end-1), and then add the two together.

If you step through this example, you can tell that there is a lot “recalculating” that occurs to return the value. There’s actually a more efficient way to calculate Fibonacci numbers (so keep reading).

Tail-recursive functions

Tail-recursion is a special type of recursion that is completely self-contained. That is, all of the information needed to calculate the return value of the function is stored within the function itself. You can tell whether a function is tail recursive if there is no extra “bit” beyond returning the recursive function.

Here’s an example of a tail-recursive Fibonacci function.

(So, a quick side note here: I put in a few keyword arguments into this function for ease (num1, num2, and count). Because the keyword value of a function is only instantiated the first time the function is run, if you want to use a keyword argument in a recursive function, you need to pass the argument as an immutable value. In this case, I’ve used “None.” Thanks, Stack Overflow!)

If you step through the function below, you can see that this function takes fewer steps than the non-tail recursive function. But there’s an even more efficient way to calculate Fibonacci numbers.

Unrolling tail-recursive functions

Because tail-recursive functions are self-contained, they can be rewritten as while loops. This is called unrolling the recursion.

Here’s what that looks like in Python:

Notice that the while loop function takes even fewer steps than the tail-recursive function. While loops are useful because they are more efficient than tail-recursive functions. The downside is that they can be a little more difficult to understand when things get more complex.

An example of recursion in practice

In my program, N Degrees of Wikipedia, I use a recursive function to return a particular value. This program searches Wikipedia to find a path connecting a beginning page to an end page through the links on the beginning page in a certain number of degrees. If the search is successful, the path between the two pages is returned along with the degree count. To find the return path, I use a tail-recursive function to find the return path between the two pages.

When I call the function, the program has already found the end page within the given number of degrees. Now it needs to find the path connecting the end page to the beginning page. It takes the url (which is the end Wikipedia page that it found) and looks up its predecessor url in the SQL database created in an earlier step. Then it takes that predecessor url, and looks up its predecessor, and so on until the predecessor url is equal to the beginning url. When this occurs, the path between beginning and end pages is complete. (You can tell that this is a tail-recursive function because the return value is completely self-contained.)

Because this is a tail-recursive function, I could just as easily have written this function as a while loop. The function below works out just the same.

Concluding thoughts

So that’s recursion in a nutshell. It can be a bit mind-bending to get your head around at first, but with practice, it can be a clean, elegant way to write functions.