Python 101: Recursion

Recursion is a topic in mathematics and computer science. In computer programming languages, the term, recursion, refers to a function that calls itself. Another way of putting it would be a function definition that includes the function itself in its definition. One of the first warnings I received when my computer science professor talked about recursion was that you can accidentally create an infinite loop that will make your application hang. This can happen because when you use recursion, your function may end up invoking itself infinitely. So as with any other potential infinite loop, you need to make sure you have a way to break out of the loop. The idea in most recursive functions is to break up the procedure being done into smaller pieces that we can still process with the same function.

The favorite method of describing recursion is usually illustrated by creating a factorial function. A factorial normally looks something like this: 5! Note that there is an exclamation mark after the number. That notation denotes that it is to be treated as a factorial. What this means is that 5! = 5*4*3*2*1 or 120.

Let’s take a look at a simple example.

# factorial.py

def factorial(number):
    if number == 0:
        return 1
    else:
        return number * factorial(number-1)

if __name__ == '__main__':
    print(factorial(3))
    print(factorial(5))

In this code, we check the number that we pass in to see if it is equal to zero. If it is, we return the number one. Otherwise we take the number and multiple it with the result of calling the same function but with the number minus one. We can modify this code a bit to get the number of times we have recursed:

def factorial(number, recursed=0):
    if number == 0:
        return 1
    else:
        print('Recursed {} time(s)'.format(recursed))
        recursed += 1
        return number * factorial(number-1, recursed)

if __name__ == '__main__':
    print(factorial(3))

Each time we call the factorial function AND the number is greater than zero, we print out the number of times we recursed. The last string you should see should be “Recursed 2 time(s)” because it should only need to call factorial twice with the number 3.

---

Python’s Recursion Limit

At the beginning of this article I mentioned that you can create an infinite recursive loop. Well you can in some languages, but Python actually has a recursion limit. You can check it yourself by doing the following:

>>> import sys
>>> sys.getrecursionlimit()
1000

If you feel that limit is too low for your program, you can also set the recursion limit via the sys module’s setrecursionlimit() function. Let’s try to create a recursive function that will exceed that limit to see what happens:

# bad_recursion.py

def recursive():
    recursive()

if __name__ == '__main__':
    recursive()

If you run this code, you should see the following exception thrown: RuntimeError: maximum recursion depth exceeded

Python prevents you from creating a function that ends up in a never-ending recursive loop.

---

Flattening Lists with Recursion

There are other things you can do with recursion besides factorials though. A more practical example would be creating a function to flatten a nested list, for example:

# flatten.py

def flatten(a_list, flat_list=None):
    if flat_list is None:
        flat_list = []

    for item in a_list:
        if isinstance(item, list):
            flatten(item, flat_list)
        else:
            flat_list.append(item)

    return flat_list

if __name__ == '__main__':
    nested = [1, 2, 3, [4, 5], 6]
    x = flatten(nested)
    print(x)

When you run this code, you should end up with a list of just integers instead of a list of integers and one list. Of course there are many other valid ways to flatten a nested list, such as using Python’s itertools.chain(). you might want to check out the code behind the chain() class as it has a very different approach for flattening a list.

---

Wrapping Up

Now you should have a basic understanding of how recursion works and how you can use it in Python. I think it’s neat that Python has a built-in limit for recursion to prevent developers from creating poorly constructed recursive functions. I also want to note that in my many years as a developer, I don’t think I have ever really needed to use recursion to solve a problem. I am sure there are plenty of problems where the solution could be implemented in a recursive function, but Python has so many other ways to do the same thing that I’ve never felt the need to do so. One other note I want to bring up is that recursion can be difficult to debug since it is hard to tell what level of recursion that you have reached when the bug occurred.

Regardless, I hope you have found this article useful. Happy coding!

---

Related Reading

• How to Think Like a Computer Scientist – Chapter 3
• StackOverflow – How can I build a recursive function in python?
• Python Practice Book – Functional Programming