7.8 Branching recursion

When we taught you recursion, we started with sum_nested:

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

sum_nested is different from sum_ordinary in a very important way: A call to this function either doesn’t recurse or recurses not once, but n times, where n is len(obj). And each of these calls either doesn’t recurse or recurses potentially several times. And so on and so on. We call this branching recursion because we end up with a branching set of function calls. We can represent this with a branching diagram. For example, suppose we have a main block that calls sum_nested([6, [1, [2, 4], [3]], [], [8]]). This ultimately leads to all the function calls shown in the diagram below, where an arrow from A to B means that function call A leads to function call B.

Because of the branching calls, the set of actions that occurs on the call stack in this case is much more complicated than what we saw with sum_ordinary. Try to answer these questions:

1. How many frames are on the stack when we are processing the call to sum_nested(6) (including the stack frame for that call)?

2. How many frames are on the stack when we are processing the call to sum_nested([8]) (including the stack frame for that call)?

3. How many frames are on the stack when we are processing the call to sum_nested([2, 4]) (including the stack frame for that call)?

4. How many frames are on the call stack when it reaches its tallest?

Can you picture exactly all the pushing and popping that must go on to execute this simple call to sum_nested([6, [1, [2, 4], [3]], [], [8]])? Python is infinitely “patient” and happily works away on this. But for people, it’s hard to hold in our head, and it can be much more complex when the function call isn’t so trivial. We could trace carefully on paper, working away on the pushing and popping just as Python does, but that is a lot of work. Luckily, we know that we don’t have to because partial tracing, although much simpler, works.

This is why partial tracing is so great!