An Introduction to Recursion in Python

Code along video

Learning objectives

In this code along, we introduce recursion, in which a function calls itself as a subroutine. We will write recursive versions of a few familiar functions before applying recursion to trees in the next code along.

Code along summary

Setup

Create a new directory python/src/recursion and add a new main.py file there containing the following starter code.

def main():
    print("Recursion in Python.")

if __name__ == "__main__":
    main()

Summing integers, a third way

Near the start of this course, we wrote a function that takes an integer n and returns the sum of the first n positive integers. We solved this problem with a for loop and with a while loop, and Gauss would tell us that we don’t need a loop at all, since the sum is equal to n*(n+1)/2. We will now see a third approach.

Say that we are asked to sum the first 50 positive integers, and we don’t know Gauss’s formula. Being bad at arithmetic, we could remember the number 50 and ask a friend for the sum of the first 49 positive integers, planning to add 50 to whatever they tell us. Our friend, who is also bad at arithmetic, remembers 49 and delegates the sum of the first 48 integers to another friend, and so on down a chain of 50 people. Eventually, someone asks the last friend in the chain for the sum of the first 1 positive integer, and that friend just returns 1. The answer then works its way back up the chain, as each friend adds the number they remembered, until it reaches us. The idea is to remember n and aggressively delegate the sum of the first n – 1 integers to a minion, except that in this case, the minion is the function itself.

Every recursive algorithm has two kinds of cases. The easiest case, being the last minion, is called the base case; here, if n is 0, we return 0, and if n is 1, we return 1. The remaining cases are where delegation happens, and they are called the inductive step. The inductive step applies a recurrence relation, which is a formula for something in terms of smaller inputs to the function. In our case, the sum of the first n integers is n plus the sum of the first n – 1 integers.

def sum_integers(n: int) -> int:
    """Returns sum of first n positive integers."""
    if n < 0:
        raise ValueError("input cannot be negative.")

    # Gauss would say: n*(n+1)/2
    # idea: remember n, aggressively delegate sum of first n-1 integers to a minion
    # every recursive algorithm has two cases
    # easiest case is to be the last minion
    # (base case)
    if n == 0:
        return 0
    if n == 1:
        return 1

    # remaining cases are where delegation happens
    # inductive step applies a recurrence relation, or a formula for something in terms of smaller inputs to the function
    # s(n) = n + s(n-1)
    return n + sum_integers(n-1)

By the time we reach the final line, we know that n is greater than 1, since otherwise we would have already raised an error or returned a value. Calling sum_integers() from within sum_integers() may look strange, but every modern programming language supports it.

Factorial

We can apply the same idea to compute n!, the product of the first n positive integers. If n is negative, we raise an error. Our base case is that both 0! and 1! are equal to 1. For the inductive step, we notice that n! = n * (n-1) * ... * 2 * 1, which is just n times (n-1)!.

def factorial(n: int) -> int:
    """Return n! for a given integer n as input."""
    if n < 0:
        raise ValueError("Negative input.")

    # base case
    if n == 0 or n == 1:
        return 1   # 0! = 1

    # inductive step
    # n! = n * (n-1) * (n-2) * ... * (2) * (1)
    # n! = n * (n-1)!
    return n * factorial(n-1)

Fibonacci numbers

Finally, let’s compute Fibonacci numbers, which we also saw near the start of the course. The sequence begins 1, 1, 2, 3, 5, 8, 13, …, where each term after the first two is the sum of the previous two terms. We will index the sequence starting at 0, so that fibonacci(0) and fibonacci(1) are both equal to 1. This is our first base case that covers more than one value. The inductive step is the recurrence relation F(n) = F(n-1) + F(n-2).

def fibonacci(n: int) -> int:
    """Return the n-th Fibonacci number, where the sequence is
    given as (1, 1, 2, 3, 5, 8, 13, ...). Each number is the sum of the
    previous two terms, and the first two terms are 1."""
    if n < 0:
        raise ValueError("Negative input.")

    if n == 0 or n == 1:
        return 1  # base case

    # for the inductive step, we know that F(n) = F(n-1) + F(n-2)
    return fibonacci(n-1) + fibonacci(n-2)

Testing our functions

Let’s make sure that our functions work by calling them in main().

def main():
    print("Recursion in Python.")

    print("Sum of first 100 integers is", sum_integers(100))
    print("10 factorial is", factorial(10))
    print("fibonacci number at index 8 of the sequence is", fibonacci(8))

Navigate into python/src/recursion and run python3 main.py. The sum of the first 100 integers is 5050, as Gauss would have told us, and 10! is 3,628,800. Since our sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, …, the term at index 8 is 34, which matches our output.

Recursion in Python.
Sum of first 100 integers is 5050
10 factorial is 3628800
fibonacci number at index 8 of the sequence is 34

Big tree bad

It would be tedious to compute Fibonacci numbers by hand, so let’s ask our function for the Fibonacci number at index 100.

print("Fibonacci number at index 100 of the sequence is", fibonacci(100))

The best explanation that a student ever gave for this issue was just three words: big tree bad. The figure below shows the function calls made when computing the seventh Fibonacci number with a version of the function in which the first two terms are fib(1) and fib(2). The call fib(7) calls fib(6) and fib(5) and waits for them to finish; each of those calls two more functions, and so on.

When we summed integers or computed factorials, each call delegated its work to a single minion, so computing sum_integers(100) required only 100 function calls. When we compute Fibonacci numbers, each call branches into two calls. Worse, the calls do not know about each other, so the same work is repeated over and over; for example, fib(3) is computed separately in many different parts of the tree. The number of calls grows roughly like 2ⁿ, so computing fibonacci(100) would take far longer than we could ever wait, even though computing the 100th Fibonacci number by hand only takes about 100 additions.

You may already have fixed this problem in one of our exercises from the start of the course, which asked you to compute the n-th Fibonacci number with a loop. Recursion is a beautiful idea, but this example shows that it is not always the right tool for the job.

Looking ahead

For summing integers or computing factorials, a loop or a formula works just as well as recursion. In the next code along, we will see a context in which recursion is the vastly superior approach: counting the leaves in a tree, which is the last function that we need to run UPGMA.