# 7.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

```python
[[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 `lst_i` is called a *sub-nested-list* of the outer list.

    We allow `n == 0`, which represents an *empty list*---this counts as a "nested list".

This is a **recursive definition**: it defines nested lists in terms of other nested lists.[^1]
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 chapter, 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, including the outermost set of square brackets.
For example:

- The depth of a single integer like `10` is 0, since there are no lists.
- The depth of `[1, 2, 3]` is 1. The depth of the empty list `[]` is also 1.
- The depth of `[1, [2, [3, 4], 5], [6, 7], 8]` is 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:

```python
def sum_nested(obj: 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.


[^1]: Another term for "recursive definition" is *self-referential definition*.