# 7.4 Writing Recursive Functions: Using the Recursive Structure of the Problem

We've spent some time learning how to understand a recursive function using partial tracing.
Now let's think about how to write one.
The same kind of recursive thinking we used when partial tracing will serve us well.

One way to approach writing a recursive function is to start with the
recursive structure of the problem itself.
For example, consider a function that takes a nested list as input.
An arbitrarily complex nested list is made up of less complex nested lists,
and what is getting less complex (or smaller) is the depth.
You can see this visually by examining the number of nested brackets, which is
always 1 less in a sublist of a list than in the list itself.
We can solve a problem for a deeply nested lists in terms of solutions to the problem on
the less deep sublists within it.

Here is a design recipe for this approach:

1.  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 defined 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:

    ```python
    def f(obj: int | list) -> ...:
        if isinstance(obj, int):
            ...
        else:
            for sublist in obj:
                ... f(sublist) ...
    ```

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

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

4.  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!


## What about empty lists?

Here is our recursive template for nested list functions, repeated from above.

```python
def f(obj: int | list) -> ...:
    if isinstance(obj, int):
        ...
    else:
        for sublist in obj:
            ... f(sublist) ...
```

We've emphasized this structure as a way to separate the logic of the *base case* of the function, when `obj` is an integer, from the *recursive case* of the function, when `obj` is a list.
However, there is one subtlety we skipped over earlier: what happens when `obj` is an empty list?
To make this concrete, let's return to our `sum_nested` function:

```python
def sum_nested(obj: int | list) -> int:
    """Return the sum of the numbers in a nested list <obj>.
    """
    if isinstance(obj, int):
        return obj
    else:
        s = 0
        for sublist in obj:
            s += sum_nested(sublist)
        return s
```

What happens if we call `sum_nested([])`?
In this case, the if condition is `False`, we enter the else branch, which we've been calling the "recursive case" up to this point.
However, in this case because `obj` is empty, the for loop won't iterate, and so the initial value of `s`, `0`, will be returned.[^4]
No recursive calls are made, since there are no sub-nested-lists to recurse into.

Technically, this makes the empty list `[]` another *base case input* for this function.
We could write this more explicitly in our implementation of `sum_nested` as follows:

```python
def sum_nested(obj: int | list) -> int:
    """Return the sum of the numbers in a nested list <obj>.
    """
    if isinstance(obj, int):  # Base case 1: obj is an integer
        return obj
    elif obj == []:           # Base case 2: obj is an empty list
        return 0
    else:                     # Recursive step: obj is a non-empty list
        s = 0
        for sublist in obj:
            s += sum_nested(sublist)
        return s
```

You might prefer this version, because even though it's a bit longer, it is more explicit in identifying the "empty list" base case.
If so, we encourage you to use this explicit `elif obj == []` check in your own recursive functions on nested lists!

<!-- ## Nested list exercises

After you complete these nested list exercises, you should reach a point where you think that all of these questions are basically the same, because they are!
It's actually quite amazing how much the fact that the underlying input---a nested list---influences what our code looks like.

1. Compute the *depth* of a nested list, which is the maximum level of nesting in the list. An integer has depth 0.
2. Compute the number of times a number (given as a parameter) occurs within a nested list.
3. Return a list containing all the odd numbers in a nested list, in the order they appear in the list.
4. Return a list containing all the odd numbers in a nested list, in the *reverse* order they appear in the list.
5. Return all the items at a certain depth (given as a parameter) in a nested list. -->


<!--
## Some common questions

There were two common questions that came up during this week's lab. Please keep in mind that in order to use recursion in your own code, the answers to these questions are irrelevant; you can *reason* about your recursive code by following the method described above, without actually knowing any implementation details.

But in terms of implementation, there is one overriding principle: recursive function calls behave *exactly the same* as any other function calls. So if you're ever asking a question about how recursion works under the hood, try asking the equivalent question replacing the recursive call with a call to some other helper function, and see if you know the answer.

### Why do we need a return in the recursive step?

The question is, since the recursive step triggers a recursive call, which will trigger another recursive call, etc., all the way until reaching the base case, then why can't we rely on the base case returning the correct value, and omit any `return` statements in the recursive step?

```python
def sum_nested(obj):
    if isinstance(obj, int):
        return obj
    else:
        s = 0
        for sublist in obj:
            s = s + sum_nested(sublist)
        # omit return?
        s
```

The answer to this question lies not in the behaviour of recursive functions, but in the behaviour of `return` statements and functions. Consider this (example:

```python
def f():
    return 5

def g():
    f()
```

What happens when we call `g`?

1. `g` calls `f`
2. `f` returns 5 to `g`
3. `g` takes the 5 and... stops.

In other words, `g` returns `None`, not 5! And this is true *regardless of the body of* `f`; it completely depends on the *lack* of `return` in `g`.

The same is true of recursive functions: without even looking carefully inside the `for` loop, we can determine that the recursive step will always return `None`, because it doesn't use `return` anywhere! So the moral of the story is that any time you want a function or method to return something, you must use the keyword `return`.

### Do recursive calls overwrite local variables?

Our code for `sum_nested` uses local variable `s` to accumulate the nested sums of each inner nested list. But each time we make a recursive call, the line `s = 0` executes; why doesn't the local variable `s` get overwritten in each recursive call?

This is one of the fundamental features of functions in almost all programming languages: every *function call* has its own namespace of local variables. In other words, every time you make a function call, it gets its own "set" of local variables, which cannot be influenced by any other function call.
This is true when one function calls another:

```python
def f():
    x = 5

def g():
    x = 100
    f()
    return x  # Returns 100
```

It is just as true when a function calls itself. So in fact multiple recursive calls never "overwrite" local variables, because each call has its own local variables that are independent from all other calls.

## Warning about recursive calls

Finally, we return to the "fundamental assumption" we made when reasoning about recursive code: that every recursive call always works properly. This is a powerful assumption because it greatly simplifies how we can trace our code, but it does come with one caveat.

**We can only assume a recursive call is correct when the argument is "smaller" than the original input to the function.** What do we mean by smaller? This depends on the type of input, but generally we mean "structurally closer to the base case." For example, in nested lists the base cases are the integers, i.e., nested lists of depth 0. In our recursive calls, each `sublist` has a smaller depth than the original list, and here "smaller depth" is our indication that these recursive calls are made on smaller inputs.

Here is an example of a bad recursive call, where the depth might actually stay the same between the original input and the input to the recursive call:

```python
def sum_nested(obj):
    if isinstance(obj, int):
        return obj
    else:
        s = 0
        for sublist in obj:
            s = s + sum_nested([sublist, 1])
        return s
```

In the recursive call, the input might look "smaller" than the original.
After all, it contains only one element of obj with the number 1 added in.
But the base case we are working towards occurs when obj is simply an int,
and we can progress towards it by reducing the *depth* of the list on every call.
In the above version of the function, we don't reduce the depth at all.
For instance, if `obj` is a list of depth 2 such as `[[10, 20, 30], [2, 4], 88]`,
on the first iteration of the loop `sublist` is `[10, 20, 30]`
and so the argument passed in the recursive call is `[[10, 20, 30], 1]`.
This is also a list of depth 2.  We have not progressed towards the base case.
As a result,
calling this version of the function results in *infinite recursion*,
which actually gives us a special runtime error in Python:

```python
>>> sum_nested([1, 2, 3])
RuntimeError: maximum recursion depth exceeded while calling a Python object
```

We'll talk more about this error later in the course, but for now keep in mind that the "size" of the inputs to recursive calls must always be smaller than the original!

This is one reason we placed such a big emphasis on identifying the recursive structure of the input and problem: if you do so, and respect that structure in your recursive calls, you are almost guaranteed to avoid this problem. This is true for not just nested lists, but also the recursive linked list implementation you saw in Lab 5, and the new recursive data structure we'll see next week.

-->

## What if the problem lacks a recursive structure?

Later on, we'll learn some other structures that can be defined recursively, and each
will have its own code template.
These templates can be really helpful in solving recursive problems.

An interesting challenge arises when we need to solve a problem that does not come
with a recursive structure.
Here's an example:

```python
def buyable(n: int) -> bool:
    """Return whether one can buy exactly <n> McNuggets.

    McNuggets come in boxes of 4, 6, and 25. It is considered possible
    to buy exactly 0 McNuggets.

    Precondition: n >= 0
    """
```

The input to this function is an integer.
Unlike nested lists,
integers do not have an obvious recursive structure, and so we need to do additional problem-solving to find a recursive solutions to this function.
One such technique is to generate test scenarios, which is described in the next section.



[^4]: The return value of 0 may seem a bit strange. This is because it is often mathematically useful to define the sum of an empty sequence to be zero. Python's built-in `sum` function returns 0 on an empty list---try it!