7.1 Motivation: Adding Up Numbers

This week, we’re going to learn about a powerful technique called recursion, which we’ll be using in various ways for the rest of the course. However, recursion is much more than just a programming technique, it is a way of thinking about solving problems. This new way of thinking can be summarized in this general strategy: identify how an object or problem can be broken down into smaller instances with the same structure.

Let’s begin with a series of problems that will demonstrate the need for recursion.

Summing lists and nested lists

Consider the problem of computing the sum of a list of numbers. Easy enough:

def sum_list(lst: list[int]) -> int:
    """Return the sum of the items in a list of numbers.

    >>> sum_list([1, 2, 3])
    6
    """
    s = 0
    for num in lst:
        s += num
    return s

But what if we make the input structure a bit more complex: a list of lists of numbers? After a bit of thought, we might arrive at using a nested loop to process individual items in the nested list:

def sum_list2(lst: list[list[int]]) -> int:
    """Return the sum of the items in a list of lists of numbers.

    >>> sum_list2([[1], [10, 20], [1, 2, 3]])
    37
    """
    s = 0
    for list_of_nums in lst:
        for num in list_of_nums:
            s += num
    return s

And now what happens if we want yet another layer, and compute the sum of the items in a list of lists of lists of numbers? Some more thought leads to a “nested nested list”:

def sum_list3(lst: list[list[list[int]]]) -> int:
    """Return the sum of the items in a list of lists of lists of numbers.

    >>> sum_list3([[[1], [10, 20], [1, 2, 3]], [[2, 3], [4, 5]]])
    51
    """
    s = 0
    for list_of_lists_of_nums in lst:
        for list_of_nums in list_of_lists_of_nums:
            for num in list_of_nums:
                s += num
    return s

Of course, you see where this is going: every time we want to add a new layer of nesting to the list, we add a new layer to the for loop. Note that this is quite interesting from a “meta” perspective: the structure of the data is mirrored in the structure of the code which operates on it.

Simplifying using helpers

You might have noticed the duplicate code above: in fact, we can use sum_list as a helper for sum_list2, and sum_list2 as a helper for sum_list3:

def sum_list(lst: list[int]) -> int:
    """Return the sum of the items in a list of numbers.
    """
    s = 0
    for num in lst:
        # num is an int
        s += num
    return s

def sum_list2(lst: list[list[int]]) -> int:
    """Return the sum of the items in a list of lists of numbers.
    """
    s = 0
    for list_of_nums in lst:
        # list_of_nums is a list[int]
        s += sum_list(list_of_nums)
    return s

def sum_list3(lst: list[list[list[int]]]) -> int:
    """Return the sum of the items in a list of lists of lists of numbers.
    """
    s = 0
    for list_of_lists_of_nums in lst:
        # list_of_lists_of_nums is a list[list[int]]
        s+ = sum_list2(list_of_lists_of_nums)
    return s

While this is certainly a nice simplification, it does not generalize very nicely. If we wanted to implement sum_list10, a function which works on lists with ten levels of nesting, our only choice with this approach would be to first define sum_list4, sum_list5, etc., all the way up to sum_list9.

Heterogeneous lists

There is an even bigger problem: no function of this form can handle nested lists with a non-uniform level of nesting among its elements, like

[[1, [2]], [[[3]]], 4, [[5, 6], [[[7]]]]]

We encourage you to try running the above functions on such a list—what error is raised?