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

```python
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:

```python
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":

```python
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`:

```python
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

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

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