Ctrl+K

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

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:

    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.

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:

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:

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!

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:

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.

Contents