What is recursion?

Let's talk about recursion.

Recursive functions call themselves

Here's a Python script that counts up to a given number:

from argparse import ArgumentParser


def count_to(number):
    for n in range(1, number+1):
        print(n)


def parse_args():
    parser = ArgumentParser()
    parser.add_argument("stop", type=int)
    return parser.parse_args()


def main():
    args = parse_args()
    count_to(args.stop)


if __name__ == "__main__":
    main()

Note that the main function in that program calls the parse_args function as well as the count_to function.

Functions can call other functions in Python. But functions can also call themselves!

Here's a function that calls itself:

def factorial(n):
    if n < 0:
        raise ValueError("Negative numbers not accepted")
    if n == 0:
        return 1
    return n * factorial(n-1)

A function that calls itself is called a recursive function.

It might seem like a bad idea for a function to call itself and it often is a bad idea... but not always.

Beware infinite recursion

If a function calls itself every time it's called, the code would run forever. Fortunately, Python will stop potentially endless recursion by enforcing a maximum recursion depth, which defaults to 1,000:

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

So if we try to call this f function, which always calls itself, we'll see a traceback which says a RecursionError exception was raised:

>>> def f(n):
...     print(n)
...     f(n+1)
...
>>> f(0)
0
1
2
3
...
995
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in f
  File "<stdin>", line 3, in f
  File "<stdin>", line 3, in f
  [Previous line repeated 993 more times]
  File "<stdin>", line 2, in f
RecursionError: maximum recursion depth exceeded while calling a Python object
996

To avoid RecursionError exceptions, our recursive functions should always have a base case which stops our function from calling itself yet again.

For example, this factorial function has a base case of 0 (or any number below 0):

def factorial(n):
    if n < 0:
        raise ValueError("Negative numbers not accepted")
    if n == 0:
        return 1
    return n * factorial(n-1)

So when we call it, instead of running forever it eventually returns a value to us:

>>> factorial(4)
24

Recursion works thanks to the call stack

When many programmers first see recursion, it seems impossible.

How could a function call itself... how would Python keep track of that?

Python keeps track of where we are within our program by using something called a call stack. The call stack is what makes it possible for functions to call other functions, and even for functions to call themselves. Whenever a function is called, Python puts a new frame on the call stack.

So when factorial was called with 4, Python put a frame on the call stack:

And since factorial called factorial again, another frame was added to the call stack:

Whenever any function is called, that function call is added to the call stack until that function returns. And each stack frame independently keeps track of its own variables.

Once we finally reach the base case in a recursive function, it'll return a value to the stack frame that called it:

And the function that value was returned to will then do a computation and eventually return a value to whichever stack frame called it:

Then that stack frame will do a computation as well, returning to the function that called it:

And so on:

Until finally, our original factorial function that we called with 4 returns the value of 24, and then our call stack is emptied:

The call stack is used for every function call. The only thing that's different in the case of recursion is that we end up with the same function name in more than one place in the call stack.

This doesn't mean that recursion is simple. Recursion can definitely be mind-bending. But recursion is possible thanks to Python's call stack.

You can walk through that factorial function call yourself with Python Tutor:

Using for loops instead of recursion

Most of the places where recursion could be use, it shouldn't be used. Most possible uses for recursion would be easier to understand as a loop.

For example, there's no reason to write a recursive function that just counts downward:

>>> def countdown(n):
...     print(n)
...     if n > 1:
...         countdown(n-1)
...
>>> countdown(3)
3
2
1

Because we could do that with a for loop instead:

>>> for n in range(3, 0, -1):
...     print(n)
...
3
2
1

Loops are often more readable and easier to maintain than a recursive function.

But recursion must be useful for something, right? It is!

Recursion's most common use case

Recursion is most often useful when the problem you're solving involves traversing or constructing a tree-like structure.

Here's a recursive function that navigates a dictionary-of-dictionaries of any depth:

def print_tree(tree, prefix=""):
    for key, value in tree.items():
        line = f"{prefix}+-- {key}"
        if isinstance(value, dict):
            print(line)
            print_tree(
                value,
                prefix=prefix + "|   ",
            )
        else:
            print(f"{line}: {value}")

When we call this function with a dictionary-of-dictionaries, it will print out the keys and values for every dictionary that it finds:

>>> tree = {
...     "a": None,
...     "b": {"b1": None, "b2": None},
...     "c": {
...         "c1": None,
...         "c2": {
...             "c21": None,
...             "c22": None,
...         },
...     },
... }
>>> print_tree(tree)
+-- a: None
+-- b
|   +-- b1: None
|   +-- b2: None
+-- c
|   +-- c1: None
|   +-- c2
|   |   +-- c21: None
|   |   +-- c22: None

Whenever this function finds a dictionary value that is also a dictionary, it will call itself with that new dictionary and a new prefix (the prefix controls the indentation for each dictionary level).

This is a great example of a function that would be very challenging to implement without recursion.

This is the kind of programming problem that recursion is perfect for.

Loops are great, but recursion does have its uses

Recursion happens when a function calls itself. The idea behind recursion is to break down a complex problem into smaller sub-problems.

It's important that every recursive function have a base case, to make sure that the recursion eventually stops.

For most problems that involve repetition, Python's for loops and while loops are better suited to the task than recursion. But recursion is pretty handy for certain types of programming problems.