6.101 Fall 2022: Recursion

In some sense, this week’s reading represents a slight shift of focus as we move on to a new topic. The ideas we’ve been talking about so far won’t go away, of course, but we will have a different central focus for the next few weeks: recursion.

We expect that recursion is something that everyone has seen before in 6.100A (i.e. 6.0001), but recursion can feel somewhat weird and uncomfortable until you build up some experience of using it and some understanding of how it works. So we’re going to spend a fair amount of time over the next couple of weeks with that goal in mind: developing facility and comfort with, and a deeper understanding of, recursion. As usual, we’ll come at this from a couple of different perspectives: we’ll certainly look at how we can use recursion in our own programs, but we’ll also focus on how recursion works behind the scenes (in terms of our environment model), as well as talking about how we can go about deciding whether a recursive solution is appropriate for a given problem (or whether some other approach might be better).

And don’t worry if recursion feels strange or uncomfortable; that’s a natural first reaction, and with time and practice (which we’re aiming to provide over the course of the next several readings, recitations, and labs), this idea will stop being quite so scary and start being a really powerful tool that we can use in our own programs.

Before we can get too far into talking about using recursion, it’s worth briefly talking about what recursion is. Generally speaking, recursion occurs when something is defined in terms of itself.

Although our focus will be on recursion from a programming perspective, recursion can also appear in other contexts. Here is an example from mathematics, a definition of the factorial operation. For nonnegative integer $\mathrm{<p>n</p>}$,

In general, a recursive definition will have multiple pieces:

• one or more base cases (terminating scenarios that do not need recursion to produce answers), and
• one or more recursive cases (sets of rules that reduce all other cases toward base cases)

In our example above, the case where $\mathrm{<p>n</p>}<p>=</p>\mathrm{<p>0</p>}$ is a base case. We don’t need recursion to find the answer there, since $\mathrm{<p>0</p>}<p>!</p><p>=</p>\mathrm{<p>1</p>}$ by definition.

The other case is our recursive case. We can see the recursion here in that figuring out that value depends on the definition of factorial. We can look at an example of this process in this mathematical context before we move on to programming. Let’s consider determining $\mathrm{<p>4</p>}<p>!</p>$ using the definition above. We can plug things into that definition and use something like the following sequence of steps to arrive at an answer, repeatedly applying the definition of factorial until we reach a base case:

In this example, we can also see the important property that the recursive case reduces us down toward a base case, in the sense that for any value $\mathrm{<p>n</p>}$ we want to compute the factorial of, the $<p>(</p>\mathrm{<p>n</p>}<p>-</p>\mathrm{<p>1</p>}<p>)</p><p>!</p>$ is applying the factorial definition to a value that is closer to our base case of $\mathrm{<p>n</p>}<p>=</p>\mathrm{<p>0</p>}$. In this way, we can rest assured that for any nonnegative integer $\mathrm{<p>n</p>}$, this process will eventually reach a base case, at which point we can find our overall answer.

Programming

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

To reinforce the idea that some problems are naturally recursive, let’s look at a quick example from a very practical program: CAT-SOOP, the software that is running the website you’re looking at right now. CAT-SOOP is written in Python. One of its tasks is to store information about submissions that are made and other events that happen while you are using it, so it has a notion of a log that records information on disk about those events.

We don’t want to get too much into the details about how CAT-SOOP does logging, but here is one part of the system that is particularly relevant to our discussion: a function that tests whether some arbitrary Python value can be stored in the log or not.

def can_log(x):
    """
    Checks whether a given value can be a log entry.
    Valid log entries are strings, ints, floats, complex numbers, None, or Booleans;
    _or_ lists, tuples, sets, frozensets, dicts, or OrderedDicts containing only valid log entries.
    """

Look at the docstring of this function: it gives us a nice description of which values can be valid log entries. What about this description suggests that recursion might be the best way to implement this function?

The docstring defines what a “valid log entry” is in a way that depends on the definition of a valid log entry!

Valid log entries are strings, ints, floats, etc. or lists, tuples, sets, etc. containing only valid log entries.

Definitions like this are extremely common in programming, data representation, and software systems in general.

How would we implement this recursively? First notice that the definition has a base case:

    if isinstance(x, (str, bytes, int, float, complex, NoneType, bool)):
        return True

If x is one of these types, then we’re done, we don’t need to do any further recursion at all.

But then we’ve also got these recursive cases: if x is one of the collection types, like list, tuple, or set, then

    elif isinstance(x, (list, tuple, set, frozenset)):
        return all(can_log(i) for i in x)

Notice the recursive call to can_log, being applied to every element of the collection (the all). Most importantly, although those elements of the collection could be simple strings or ints (base cases), they could also be lists or sets or other collections themselves, thus needing still further recursion. The recursive implementation automatically takes care of that, no matter how complex the nesting gets.

We also need to handle dictionaries, which need two recursive calls for each (key,value) pair:

    elif isinstance(x, (dict, OrderedDict)):
        return all((can_log(k) and can_log(v)) for k,v in x.items())

And finally there’s a second base case, which is if x does not have any of the types we checked for, then it’s not a valid log entry, so we need to return False. Here’s the full function:

def can_log(x):
    """
    Checks whether a given value can be a log entry.
    Valid log entries are strings/bytestrings, ints, floats, complex numbers,
    None, or Booleans; _or_ lists, tuples, sets, frozensets, dicts, or
    OrderedDicts containing only valid log entries.
    """
    if isinstance(x, (str, bytes, int, float, complex, NoneType, bool)):
        return True
    elif isinstance(x, (list, tuple, set, frozenset)):
        return all(can_log(i) for i in x)
    elif isinstance(x, (dict, OrderedDict)):
        return all((can_log(k) and can_log(v)) for k,v in x.items())
    return False

The details of this function don’t matter as much as the big picture: this is a practical problem in which the structure of the problem was such that a recursive solution really jumps out as the simplest and most appropriate way to do it.

Let’s dig into another example: summing a list of numbers:

def sum_list(x):
    """
    Compute the sum of a list of numbers, recursively.
    """
    pass

We could use the builtin function sum() to do this, of course, or we could write an iterative solution, which is what sum() is doing anyway:

def sum_list(x):
    out = 0
    for num in x:
        out += num
    return out

We’ll talk more about the tradeoffs between iteration and recursion in the next reading. For now, though, let’s try to do everything recursively. Intuition from these simple examples will help for more complicated situations where a builtin function doesn’t exist or an iterative solution is not the best way to do it.

# BASE CASE
if len(x) == 1:
    return x[0]

# RECURSIVE CASE
else:
    return x[0] + sum_list(x[1:])

So now our whole function looks like:

def sum_list(x):
    if len(x) == 1:
        return x[0]
    else:
        return x[0] + sum_list(x[1:])

Aside: Doctest

def sum_list(x):
    """
    Compute the sum of a list of numbers, recursively.

    >>> sum_list([1,2,3,4,5])
    15
    """
    if len(x) == 1:
        return x[0]
    else:
        return x[0] + sum_list(x[1:])

... # definition of sum_list

import doctest
if __name__ == '__main__':
    doctest.testmod(verbose=True)

$ python sum_list.py
Trying:
    sum_list([1,2,3,4,5])
Expecting:
    15
ok
1 passed and 0 failed.
Test passed.

def sum_list(x):
    """
    Compute the sum of a list of numbers, recursively.

    >>> sum_list([1,2,3,4,5])
    15
    >>> sum_list([])
    0
    """
    if len(x) == 1:
        return x[0]
    else:
        return x[0] + sum_list(x[1:])

Getting the Base Cases Right

def sum_list(x):
    if len(x) == 0:
        return 0
    elif len(x) == 1:
        return x[0]
    else:
        return x[0] + sum_list(x[1:])

def sum_list(x):
    if len(x) == 0:
        return 0
    elif len(x) == 1:
        return x[0]
    elif len(x) == 2:
        return x[0] + x[1]
    elif len(x) == 3:
        return x[0] + x[1] + x[1]
    else:
        return x[0] + sum_list(x[1:])

def sum_list(x):
    if not x:
        return 0
    else:
        return x[0] + sum_list(x[1:])

Now let’s think about a slightly different problem, summing lists of numbers where numbers may be inside sublists, down to an arbitrary depth:

def sum_nested(x):
    """
    >>> sum_nested([[1, 2], [3, [4, 5]], [[[[[6]]]]]])
    21
    """
    pass

The fact that the sublists can go down to arbitrary depth makes this problem feel hard. Fortunately the empty list is still our base case:

if not x:
    return 0

But what about the recursive case? Adapting the recursive case from sum_list, which peels off the first element and then adds it to the recursive sum of the remaining elements, doesn’t work here:

return x[0] + sum_nested(x[1:])

The reason it doesn’t work is that the first element x[0] is not just a number; it might be a list. When that happens, Python will give us a TypeError, because we’re trying to add a list to a number (the number returned by the recursive sum_nested call).

So let’s try distinguishing those two cases with another if test:

if isinstance(x[0], list):
    return SOMETHING + sum_nested(x[1:])
else:
    return x[0] + sum_nested(x[1:])

Now we have two recursive cases: one used when the first element is a list and another when the first element is just a number. That second case we can handle just as before. But what should SOMETHING be, when x[0] is sublist? We might try digging out elements of that sublist:

if isinstance(x[0], list):
    return x[0][0] + sum_nested(x[1:])

But this won’t be right if the sublist has more than one element (or less than 1 element!) We might fall back to iteration:

if isinstance(x[0], list):
    subtotal = 0
    for x in x[0]:
        subtotal += x
    return subtotal + sum_nested(x[1:])

But we’re trying to solve this recursively, and worse, this doesn’t work either! Is x guaranteed to be a number here? No, it could itself be another sublist. x[0] could have sublists in it down to an arbitrary depth!

Let’s take a step back. We already have a way to sum up x[0] if it’s an arbitrarily deep list of lists. That way is sum_nested itself! We just have to lean in and trust the recursion:

if isinstance(x[0], list):
    return sum_nested(x[0]) + sum_nested(x[1:])

Again, this may seem magical. We are now using sum_nested twice in the same line! Why doesn’t this end up just calling itself endlessly and never returning? The key thing to observe is that every recursive call to sum_nested is using a list that is strictly smaller or simpler in some respect, heading towards some minimum represented by the base case. Here, we have peeled apart our original nested list into two pieces, x[0] and x[1:], each of which is smaller.

Here is the full code:

def sum_nested(x):
    """
    >>> sum_nested([[1, 2], [3, [4, 5]], [[[[[6]]]]]])
    21
    """
    if not x:
        return 0
    elif isinstance(x[0], list):
        return sum_nested(x[0]) + sum_nested(x[1:])
    else:
        return x[0] + sum_nested(x[1:])

Finding the right way to decompose a problem into smaller steps is an essential part of programming, and recursion is an elegant and simple decomposition for some problems. Suppose we want to implement this function:

def subsequences(seq):
    """
    Given a tuple or list or other iterable, returns a set of tuples
    consisting of all its subsequences.
    A subsequence is a sequence of elements from seq that are in the same
    order as in seq but not necessarily adjacent.

    >>> subsequences([4,2,3])
    {(4, 2, 3), (4, 2), (4, 3), (2, 3), (4,), (2,), (3,), ()}
    """
    pass

Aside: Canonical Output For Doctest

{(4,2,3), (4,2), (4,3), (2,3), (4,), (2,), (3,), ()}
{(4,), (4,2), (4,3), (4,2,3), (2,), (2,3), (3,), ()}
{(), (2,), (2,3), (3,), (4,), (4,2), (4,2,3), (4,3)}

def subsequences(seq):
    """
    ...
    >>> list(sorted(subsequences([4,2,3])))
    [(), (2,), (2, 3), (3,), (4,), (4, 2), (4, 2, 3), (4, 3)]
    """
    pass

One Way to Do Subsequences

def subsequences(seq):
    if not seq:
        # base case
        return {()}
    else:
        # recursive case
        first = seq[0]
        rest = seq[1:]
        result = set()
        for subseq in subsequences(rest):
            result.add((first,) + subseq)
            result.add(subseq)
        return result

result = {(first,) + subseq for subseq in subsequences(rest)}
result = result | {subseq for subseq in subsequences(rest)}
return result

The recursive implementation we just saw for subsequences is only one possible recursive decomposition of the problem. We took a solution to a subproblem – the subsequences of the remaining elements after removing the first element – and used it to construct solutions to the original problem, by taking each subsequence and either adding the first element or omitting it. This is in a sense a direct recursive implementation, where we are using the existing function to solve the subproblems.

In some cases, it’s useful for the recursive case to have different parameters or different behavior than the original function. For subsequences, what if we built up a partial subsequence using the initial elements of the input sequence, using the recursive calls to complete that partial subsequence using the remaining elements? For example, suppose the input is [9,3,5]. We’ll first select 9 to be in the partial subsequence and recursively extend it with all subsequences of [3,5]; and then we’ll skip 9, use () as the partial subsequence, and again recursively extend it with all subsequences of [3,5].

Using this approach, our code now looks like this:

def subsequences(seq):
    def subsequences_starting_with(partial_subsequence, seq):
        if not seq:
            # base case
            return {partial_subsequence}
        else:
            # recursive case
            first = seq[0]
            rest = seq[1:]
            return (
                subsequences_starting_with(partial_subsequence, rest)
                | subsequences_starting_with(partial_subsequence + (first,), rest)
            )
    return subsequences_starting_with((), seq)

The subsequences_starting_with function is a recursive helper function. It needs to be a different function from the original subsequences, because it has a new parameter partial_subsequence. The recursive calls steadily extend this partial subsequence, selecting or ignoring each element in the original input sequence, until finally reaching the end of the input (the base case), at which point the partial subsequence is returned as the only result. Then the recursion backs up and fills in other possible subsequences.

The body of subsequences gets the ball rolling by calling its helper function with an initial (empty) value for the partial-subsequence parameter. Hiding the helper function as an internal function like this is a good idea, because it’s only needed inside subsequences.

(Note that this version has returned to the potential issue with making exponentially many recursive calls, but we may still prefer it for reasons like readability.)

Let’s look at another example. Suppose we want to convert an integer to a string representation with a given base, following this spec:

def number_to_string(n, b):
    """
    Given an integer n and base b (where 2 <= b <= 10),
    returns n represented as a string in base-b notation,
    without any unnecessary leading zeroes.

    >>> number_to_string(-829, 10)
    "-829"
    >>> number_to_string(5, 2)
    "101"
    >>> number_to_string(0, 10)
    "0"
    """

Let’s develop a recursive implementation of this function. One recursive case here is straightforward: we can handle negative integers simply by recursively calling for the representation of the corresponding positive integer:

if n < 0:
    return "-" + number_to_string(-n, b)

This shows that the recursive subproblem can be smaller or simpler in more subtle ways than just the value of a numeric parameter or the size of a list parameter. We have still effectively reduced the problem by reducing it from all possible integers to just positive integers.

The next question is, given that we have a positive n, say n = 829 in base 10, how should we decompose it into a recursive subproblem? Thinking about the number as we would write it down on paper, we could either start with 8 (the leftmost or highest-order digit) or 9 (the rightmost, lowest-order digit). Starting at the left end seems natural, because that’s the direction we write, but it’s harder in this case, because we would need to first find the number of digits in the number to figure out how to extract the leftmost digit. Instead, a better way to decompose n is to take its remainder modulo b (which gives the rightmost digit) and also divide by b (which gives the subproblem, the remaining higher-order digits):

digits = "0123456789"
return number_to_string(n // b, b) + digits[n % b]

In general, think about several ways to break down the problem and try to write the recursive cases. You want to find the one that produces the simplest, most natural recursive case.

It remains to figure out what the base case is and include an if statement that distinguishes the base case from this recursive case. Here is the function:

def number_to_string(n, b):
    """
    Given an integer n and base b (where 2 <= b <= 10),
    returns n represented as a string in base-b notation.

    >>> number_to_string(-829, 10)
    "-829"
    >>> number_to_string(5, 2)
    "101"
    >>> number_to_string(0, 10)
    "0"
    """
    digits = "0123456789"
    if n < 0:
        return "-" + number_to_string(-n, b)
    elif IS_BASE_CASE:
        BASE_CASE
    else:
        return number_to_string(n // b, b) + digits[n % b]

We’ve looked at several functions here and showed how to write them recursively, sometimes in different ways. Along the way, we’ve seen that:

• every recursive function needs one or more base cases and one or more recursive cases
• the recursive cases should make the problem smaller or simpler in some way
• sometimes a recursion needs to be strengthened by using a recursive helper function with additional or different parameters

We’ve focused closely on recursion in this reading, aiming to write every function recursively, even when there was an iterative approach that might have been just as natural. Next week’s reading will delve more deeply into the question of recursion vs. iteration, showing that they are interchangeable (every iterative algorithm can be made recursive, and vice versa) and discuss when it’s more natural to use one or the other.