# 7.6 How Recursive Code Can Fail

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:

1.  A base case is incorrect.
1.  A 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.
1.  One or more of the recursive calls is being made on an input that is *not* smaller.
1.  Each recursive call is indeed on a smaller input, but we don't successfully connect to a base case.

The first two types of problem are regular bugs, while the other two involve the structure
of the recursion.
Let's look at an example of each.

## Incorrect base case

Here's a variation on our `sum_nested` function where the base case is incorrect:

```python
def sum_nested(obj: int | list) -> int:
    if isinstance(obj, int):
        return 0
    else:
        s = 0
        for sublist in obj:
            s += sum_nested(sublist)
        return s
```
Try partial tracing this function on the list `[1, [2, [3, 4], 5], [6, 7], 8]`.
It will tell you that the correct answer, 36, is returned.
But if we run that example, we do not get 36!
What's going on?
When we do partial tracing, we aren't checking whether the function works
on that case;
we are checking whether it works on that case *assuming it works on smaller cases*.
And that assumption does not hold here.
This function returns the wrong answer when given any nested list that is
simply an integer (except it works on the integer 0).^[
    Can you figure out what this function will return when called on the list
    `[1, [2, [3, 4], 5], [6, 7], 8]`, without tracing it or running it?
    Hint: look at all the places where an integer is used:
    how they are initialized, added to, and returned.
    What will be the net effect of doing any number of those operations?
]

## Incorrect recursive case

Here's a function whose job is to return the maximum value in a nested list:

```python
def biggest_nested(obj: int | list) -> int:
    """Return the biggest number in a nested list <obj>.

    >>> lst = [1, [2, [33, 4], 5], [66, 7], 8]
    >>> biggest_nested(lst)
    66
    """
    if isinstance(obj, int):
        return obj
    else:
        biggest = 0
        for sublist in obj:
            b = biggest_nested(sublist)
            if b > biggest:
                biggest = b
    return biggest
```
The base case is correct,
but the recursive case doesn't (always) work, even if every recursive call does
what it's supposed to.
There is a simple logic error that has nothing to do with recursion.
Can you come up with a test case that this function will fail?

## Input not getting smaller

So far, the kinds of errors we've looked at don't really have to do with the recursion.
But there are two kinds of errors that are all about the structure of the recursive calls.
One structural problem occurs when a recursive call is made on an input that is not smaller.

Here's an example where the code is obviously wrong:

```python
def sum_nested(obj: int | list) -> int:
    if isinstance(obj, int):
        return obj
    else:
        s = 0
        s += sum_nested(obj)
        return s
```
Since we are not recursing on each sublist, this can't work.
But the problem is worse than that:
The one recursive call we do make is on the same list we were given.
This is clearly not any smaller.
Of course, that call will do the same thing,
and the recursive call *it* makes will do the same thing,
and so on forever.
We will never reach the base case, and so we end up with infinite recursion.
We say "forever", but since Python uses the call stack to record every function call,
we will have an ever-growing call stack.
And memory is finite, so Python will eventually stop our code,
raising this error:
`RecursionError: maximum recursion depth exceeded in comparison`.

This example was a little silly, since you could easily see that the code was wrong.
But infinite recursion can be much trickier to spot.
Consider this version of `sum_nested`:

```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 looks "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 only 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,
so we ultimately will get the error
`RecursionError: maximum recursion depth exceeded in comparison`.

<!-- A much more subtle example of the problem size not getting smaller:
Try to find the problem in this version of a recursive binary search function:
```python
def bsearch(lst: list[int], i: int, j: int, item: int) -> bool:
    """Return True iff item occurs in lst[i:j].

    Precondition: i <= j.

    >>> lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> bsearch(lst, 0, 10, 7)
    True
    """
    if i == j:
        # Searching an empty sublist, so item cannot be there.
        return False
    else:
        mid = (i + j) // 2
        if item < lst[mid]:
            # Go to the LHS. No need to include lst[mid] because item is less.
            return bsearch(lst, i, mid, item)
        else:
            # To to the RHS.  Include lst[mid] because item is >= lst[mid].
            return bsearch(lst, mid, j, item)
```
-->

## Not connecting to the base case

A final structural problem occurs when
the recursive calls never connect to any base case.
This function suffers from that problem:
```python
def f(n: int) -> int:
    """
    Precondition: n >= 0.
    """
    if n == 0:
        return 1
    else:
        return n + f(n - 2)
```
In this case, the input is an integer, and it does get smaller on each recursive call.
But it gets smaller by 2, and this means there are two scenarios that can crop up:
if we call the function with an even number,
each recursive call will also be a (smaller) even number,
and eventually we will call the function on 0.
That call will invoke the base case and not recurse further.
So the original function call will ultimately terminate.
(Whether or not the return value is correct is a separate matter.)
But if we call this function with an odd number,
we will never reach 0.
Instead we will recurse on a (smaller) odd number,
and so on,
ultimately reaching a call with 1 as the argument.
And here's where we get into trouble:
that call will recurse on `f(-1)`.
Of course, that call will recurse on `f(-3)`.
You can see that this will lead to recursion that only ends when
the call stack runs out of space and Python raises the error:
`RecursionError: maximum recursion depth exceeded in comparison`

To ensure that this code always terminates properly, we must have two base cases:
one reached when we start with an even input, and one reached when we start with an odd input.
Here's a version of the function that does terminate properly
(we aren't concerned here with what the function computes):
```python
def f(n: int) -> int:
    if n == 0:
        return 1
    elif n == 1:  # Adding this clause fixes the problem
        return 1
    else:
        return n + f(n - 2)
```

<!--
Notice that if the problem size went down by 3 on each recursive call,
we'd need 3 base cases.
-->

With these categories of error in mind,
let's think about how to test and debug recursive code.


## Testing and debugging recursive code

Start by running tests for scenarios that invoke the base case(s).
If they don't work, the recursive steps certainly won't!
Once your code for the base case(s) are working,
move on to more complex scenarios.

If you encounter a bug,
go back to your analysis and make sure it is correct.
If you believe it is,
then trace your method or function on each of the scenarios in your table,
being sure to use partial tracing.
(You can do your tracing on paper or in the debugger.
If tracing in the debugger,
use "step over" to get past a recursive call
without going into the details of that call.)
Keep in mind the error message you got and the line that raised it.
Often, knowing the specific error message,
plus considering the possible scenarios that could have landed you on that line,
is enough to figure out how that error could have occurred.


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

-->