5.2 Nested Lists: A Recursive Data Structure

In the previous section, we ended by articulating a fundamental limitation of our sum_list functions: they cannot handle heterogeneous nested lists like

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

In this section, we’ll overcome this limitation by using a new strategy: breaking down an object or problem into smaller instances with the same structure as the original.

To make this more concrete, let’s first identify how the object we are working with, a nested list, can be broken down into smaller instances with the same structure. We will define a new structure that generalizes the idea of “list of lists of lists of … of lists of ints”. We define a nested list as one of two types of values:

A single integer.
A list of other nested lists ([lst_1, lst_2, ..., lst_n]). Each sublist is called a sub-nested-list of the outer list.

This is a recursive definition: it defines nested lists in terms of other nested lists. Another term for “recursive definition” is self-referential definition. It may seem a bit odd that we include “single integers” as nested lists; after all, isinstance(3, list) is False in Python! As we’ll see a few times in this section, it is very convenient to include this part of our recursive definition, and makes both the rest of the definition and the subsequent code we’ll write much more elegant.

The depth of a nested list is the maximum number of times a list is nested inside other lists, and we will define the depth of a single integer to be 0. So [1, 2, 3] has depth 1, and

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

has depth 3.

Summing up a nested list

We can use this definition to guide the design of a function that computes the sum on a nested list of numbers:

def sum_nested(obj: Union[int, List]) -> int:
    """Return the sum of the numbers in a nested list <obj>.
    """
    if isinstance(obj, int):
        # obj is an integer
        return obj
    else:
        # obj is a list of nested lists: [lst_1, ..., lst_n]
        s = 0
        for sublist in obj:
            # each sublist is a nested list
            s += sum_nested(sublist)
        return s

This is our first example of a recursive function: a function that calls itself in its body. Just as we defined a recursive data structure—nested lists—we have now defined a recursive function that operates on nested lists. Notice how the structure of the data informs the structure of the code: just as the definition of nested lists separates integers and lists of nested lists into two cases, so too does the function sum_nested. And as the recursive part of the definition involves a list of nested lists, our code involves a loop over a list, binds sublist to each inner nested list one at a time, and calls sum_nested on it to compute the sum.

We call the case where obj is an integer the base case of the code: implementing the function’s behaviour on this type of input should be very straightforward, and not involve any recursion. The other case, in which obj is a list, is called the recursive case: solving the problem in this case requires decomposing the input into smaller nested lists, and calling sum_nested on these individually to solve the problem. The example above is the simplest type of recursive function, one that has just one base case and one recursive case. Later on, we’ll look at more complex recursive data structures and functions.

Partial tracing: reasoning about recursive calls

We say that the call to sum_nested inside the for loop is a recursive function call, since it appears in the body of sum_nested itself. Such function calls are handled in the same way as all other function calls in Python, but the nature of recursion means that a single initial function call often results in many different calls to the exact same function.

When given a function call on a very complex nested list argument, beginners will often attempt to trace through the code carefully, including tracing what happens on each recursive call. Their thoughts go something like “Well, we enter the loop and make a recursive call. That recursive call will make this other recursive call, which will make this other recursive call, and so on.” This type of literal tracing is what a computer does, but it’s also extremely time-consuming and error-prone for humans to do.

Instead, whenever we are given a recursive function and a particular input we want to trace the function call on, we use the technique of partial tracing, which we’ll describe now. There are two cases.

Case 1: The input corresponds to a base case

For example, suppose we want to trace the call sum_nested(5). The input 5 is an integer, the simplest kind of nested list. In our recursive function, this corresponds to the if condition being true, and so to trace our code we can simply trace the if branch directly, completely ignoring the else branch!

def sum_nested(obj: Union[int, List]) -> int:
    """Return the sum of the numbers in a nested list <obj>.
    """
    if isinstance(obj, int):
        # obj is an integer
        return obj
    else:
        ...

Tracing this is pretty easy: the line of code return obj simply returns the input, which was 5. This is the correct result: sum_nested(5) should return 5, since the sum of a single integer is just the integer itself.

Case 2: The input corresponds to a recursive case

For example, suppose we want to trace the call sum_nested([1, [2, [3, 4], 5], [6, 7], 8]) and verify that the output is the correct value of 36. This input corresponds to the else branch of sum_nested, which we show below:

    else:
        # obj is a list of nested lists: [lst_1, ..., lst_n]
        s = 0
        for sublist in obj:
            # each sublist is a nested list
            s += sum_nested(sublist)
        return s

This code is an instance of the accumulator pattern, in which we loop over obj, and for each value update the accumulator variable s. Naive tracing is challenging, though, because at each loop iteration we’ll make a recursive call to sum_nested, which may result in tracing many subsequent recursive calls until we finally can update our accumulator.

So the key idea of partial tracing is the following: we’ll trace through the above code, but every time there’s a recursive call, instead of tracing into it, we assume it is correct, and simply use the correct return value and continue tracing the rest of our code. In the PyCharm debugger, this is analogous to using Step Over rather than Step Into when we reach a function call.

To facilitate this, we use a table of values, that we build up as follows.

First, we take our input obj, [1, [2, [3, 4], 5], [6, 7], 8], and identify each sub-nested-list. Note that there are only four of them (we don’t count sub-nested-lists of sub-nested-lists).

sublist

1

[2, [3, 4], 5]

[6, 7]

8
Next, beside each one we write down what sum_nested should return on each input. Remember that we aren’t doing any tracing here; instead, we’re filling this in based on the documentation for sum_nested.

sublist sum_nested(sublist)

1 1

[2, [3, 4], 5] 14

[6, 7] 13

8 8
Finally, we trace through the code from the original else block, updating the value of the accumulator s using the above table. We show these updates in tabular form below.

sublist sum_nested(sublist) s

N/A N/A 0 (initial value)

1 1 1 (s += 1)

[2, [3, 4], 5] 14 15 (s += 14)

[6, 7] 13 28 (s += 13)

8 8 36 (s += 8)

`sublist`
`1`
`[2, [3, 4], 5]`
`[6, 7]`
`8`

`sublist`	`sum_nested(sublist)`
`1`	`1`
`[2, [3, 4], 5]`	`14`
`[6, 7]`	`13`
`8`	`8`

`sublist`	`sum_nested(sublist)`	`s`
`N/A`	`N/A`	`0` `(initial value)`
`1`	`1`	`1` `(s += 1)`
`[2, [3, 4], 5]`	`14`	`15` `(s += 14)`
`[6, 7]`	`13`	`28` `(s += 13)`
`8`	`8`	`36` `(s += 8)`

From our table, we see that after the loop completes, the final value of s is 36, and this is the value returned by our original call to sum_nested. It also happens to be the correct value!

Why does partial tracing work?

When students first see the partial tracing technique, they are often suspicious: “What do you mean you can assume that the recursive calls are correct? What if they aren’t?!” In other words: yes, this technique is simpler, but why should we trust it?

It turns out that this assumption is valid, as long as both of the following properties hold:

You are sure that your base case is correct. (You can usually fully trace the code directly to determine this.)
Every time you make a recursive call, it is on a smaller input than the original input.If we are recursing on a nested list, a “smaller” input is one with less depth. Because we recurse on a sub-nested-list of the original, it is guaranteed to have less depth.

Here’s how to apply these ideas to show that sum_nested is correct:

Since I’m confident in the base case for sum_nested, I now know that sum_nested is correct for all nested lists of depth 0.
If I have a nested list of depth 1, every recursive call I make is going to be on a nested list of depth 0. I’m going to assume that they’re correct (because of my previous statement). So then using partial tracing, I’m confident that sum_nested is correct for all nested lists of depth 1.
If I have a nested list of depth 2, every recursive call I make is going to be on a nested list of depth 0 or 1. I’m going to assume that they’re correct (because of my previous two statements). So then using partial tracing, I’m confident that sum_nested is correct for all nested lists of depth 2.
And so on.

This idea is formalized in the Principle of Mathematical Induction, a formal proof technique that you’ll learn about in CSC165/240. It’s beyond the scope of this course, but rest assured that it tells us that partial tracing is a valid technique for reasoning about the correctness of recursive functions.

What this means for testing and debugging

The flip side of this is, if you have a recursive function and it’s incorrect (say, failing a test case that you wrote), there can only be one of the following problems:

A base case is incorrect.
One or more of the recursive calls is not being made on a smaller input.
The recursive case is incorrect, even if you assume that every recursive call is correct! In other words, the problem isn’t in the recursive call itself, it’s in the code surrounding that recursive call.

Design Recipe for recursive functions

Identify the recursive structure of the problem, which can usually be reduced to finding the recursive structure of the input. Figure out if it’s a nested list, or some other data type that can be expressed recursively.

Once you do this, you can often write down a code template to guide the structure of your code. For example, the code template for nested lists is:
```
def f(obj: Union[int, List]) -> ...:
    if isinstance(obj, int):
        ...
    else:
        for sublist in obj:
            ... f(sublist) ...
```
Identify and implement code for the base case(s). Note that you can usually tell exactly what the base cases are based on the structure of the input to the function. For nested lists, the common base case is when the input is an integer—and if you follow the above template, you won’t forget it.
Write down a concrete example of the function call on an input of some complexity (e.g., a nested list of depth 3). Then write down the relevant recursive function calls (determined by the structure of the input), and what they output based on the docstring of the function. In other words, write down the first two columns of the table we described above in the section on partial tracing.
Take your results from step 3, and figure out how to combine them to produce the correct output for the original call. This is usually the hardest step, but once you figure this out, you can implement the recursive step in your code!