Ctrl+K

7.6 How Recursive Code Can Fail

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.

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

  3. One or more of the recursive calls is being made on an input that is not smaller.

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

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:

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:

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:

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.

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:

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

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)

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.

Contents