Recursive Patterns

Table of Contents

• 1) Introduction
• 2) Definitions
• 2.1) Programming
• 2.2) Recursion in the Environment Model
• 3) Recursion in the Wild
• 4) Summing a List
• 4.1) Aside: Doctest
• 4.2) Getting the Base Cases Right
• 5) Summing a Nested List
• 6) Choosing the Right Decomposition For a Problem
• 6.1) Aside: Canonical Output For Doctest
• 6.2) One Way to Do Subsequences
• 7) Recursive Helper Functions
• 8) Choosing the Right Recursive Subproblem
• 9) Summary

1) Introduction§

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.

2) Definitions§

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 n,

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 n=0 is a base case. We don't need recursion to find the answer there, since 0!=1 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 4! 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 n we want to compute the factorial of, the (n−1)! is applying the factorial definition to a value that is closer to our base case of n=0. In this way, we can rest assured that for any nonnegative integer n, this process will eventually reach a base case, at which point we can find our overall answer.

2.1) Programming§

It turns out that Python lets us define functions recursively (i.e., we can define functions in terms of themselves). As an example, here is a Python implementation of the definition of factorial from above (note that it is almost an exact translation):

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

We could try to write this more concisely, but this is a nice form to demonstrate how this definition parallels the mathematical definition from above. There are some key things to notice here:

• This is a recursive definition, since computing factorial depends on the definition of factorial (i.e., the function calls itself in the process of computing its result in some cases).

• We have one base case. When n == 0, we can compute the result without any recursion.

• We have one recursive case, which reduces down toward a base case.

Before we move on to the details of how this works in Python, it's worth mentioning again that, depending on the extent of your prior exposure to these ideas, it may feel uncomfortable writing a function like this. And a big part of the weirdness here is that as we're writing factorial, we're using factorial as part of the body, despite the fact that we've not finished writing factorial yet! But the right strategy is to write your recursive case(s) under the assumption that you have a complete, working version of the function, and to think about, under those conditions, how would I take the result from that recursive call and combine it with other things to produce the result I'm interested in? And we don't need to have blind faith here; if we've designed things such that we have our base cases set up, and such that our recursive calls are working down toward one of those bases cases, then things will work out for us.

Another source of weirdness here is that in the process of evaluating some call to factorial, I'm going to need to call factorial again and maybe many times; and each of these calls has its own value of n. So, how can we be sure that Python is going to keep those things separate and not get confused?

2.2) Recursion in the Environment Model§

Importantly, Python is able to keep those things separate, and its ability to do so is a natural effect of our normal rules for function evaluation (that is, Python does not treat recursive functions any differently from nonrecursive functions). Let's take a look at how this plays out using an environment diagram below, for evaluating factorial(3). To start with, only proceed through step 5 below, and then answer the following question:

Moving from step 5 to step 6 in the environment diagram below, where will F_2's parent pointer go?
-- Global Frame F1 Built-ins Somewhere else.

<< First Step  < Previous Step  Next Step > Last Step >>

STEP 1
Here we have a diagram with two pieces: on the right-hand side, we have an environment diagram; and on the left-hand side, we have space to keep track of the expression we're evaluating. On the right-hand side, we see what the environment diagram looks like after executing the function definition from above, and on the left, we see the expression we are going to evaluate (factorial(3)), evaluated in the global frame (GF).

In order to perform this function call, we follow our usual steps. The first step is to figure out what function we're calling (in this case, evaluating the name factorial to find the function object on the right), as well as the arguments to the function (in this case, an integer 3). The results are shown on the next diagram.

STEP 2
Notice that we now have a new integer 3 to work with. Our next step is to set up a new frame for this function call, the result of which is shown on the next diagram.

STEP 3
Here we have our new frame (F1, which I've also labeled with some information about the function we're calling there). Notice that we have given it a parent pointer (to the enclosing frame of the function we're calling), and we've associated the name n with the argument 3 inside of F1.

With our new frame set up, we can now proceeed with evaluating the body of the function with respect to F1.

STEP 4
Evaluating the body, we start by checking if n==0. We evaluate n in F1 (finding the associated 3), which is not equal to 0, so we move on and hit return n * factorial(n-1).

This is a complicated expression, but ultimately we need to multiply two things together: the integer 3 (which we get by evaluating the name n in F1) and the result of the function call factorial(n-1).

In order to evaluate that function call, we need to evaluate the name factorial in F1 in order to figure out what function to call. Here, we don't find the name factorial in F1, so we follow its parent pointer to the global frame, where we find factorial bound to the function object at the top of the diagram; so that's the function we'll call!

Then we also need to determine the argument to this function call, which we do by evaluating n-1 with respect to F1. If we're being pedantic, Python first evaluates n (finding 3), then evaluates 1 (which makes a new integer 1), then subtracts them to get a new integer 2.

Once we know what function we're calling (the only function object drawn in the diagram) and what arguments to pass in (2), we can set up our new frame. The next slide shows the almost-complete result of that step.

STEP 5
Here we have the result of setting up that new frame but with one key piece missing: our new frame's parent pointer.

STOP HERE FOR A MOMENT AND ANSWER THE QUESTION ABOVE THE DIAGRAM BEFORE MOVING ON.

STEP 6
Here is where we need to be somewhat careful about the rules for function application! Recall that when we make a new frame for a function call, the new frame's parent pointer goes to the function's enclosing frame (i.e., the frame where that function object was defined).

Importantly, that is true regardless of what frame we're calling the function from. That is, what matters for this rule is the frame where the function was defined, not the frame from which it is being called.

STEP 7
Now that we've got our frame completely set up, we can proceed with evaluating the body of the function inside of F2.

Evaluating the body, we first check n==0 and find that that condition does not hold, so we move on and evaluate return n * factorial(n-1) with respect to F2.

Evaluating that multiplication, we find n bound to 2, and in order to figure out what to multiply by, we need to evaluate factorial(n-1). It's another function call! So we proceed with our same steps.

We start by figuring out what function we're calling and what arguments we're passing in. We find the function by evaluating the name factorial in F2. Since we don't find it there, we follow the parent pointer to the global frame, where we find the function object drawn at the top of the diagram.

Then, evaluating n-1 in F2, we get 1. So now that we have our function and our arguments, we can proceed with following our normal sequence of steps (setting up a new frame (with parent pointer), binding the parameters to the arguments that were passed in, and evaluating the body of the function in that new frame).

You may wish to pause here and try to draw the result of setting up the next frame for yourself. Where should its parent pointer go? What names should be bound in it, and to what objects are they bound? What will be the result of evaluating the body of the function in this new frame?

STEP 8
Here we see the result we arrive at after setting up our new frame F3. Notice that its parent frame is GF and that the name n is bound to the value 1.

When we evaluate the body of the function in F3, we first check n==0, and, since that evauates to False, we continue on to evaluating n * factorial(n-1) in F3. Here we have to evaluate another function call, calling the same function but now with 0 passed in. So we'll set up another frame, shown on the next step.

STEP 9
Notice that our new frame (which we'll call F4 even though I forgot to write that label next to it above) has the global frame as its parent, and it has the name n bound to 0. This has admittedly been a somewhat tedious process, but we've now arrived at a base case, and something very exciting is about to happen! Let's see what happens when we evaluate the body of the function in F4.

STEP 10
Here, we first check if n == 0, and, finally, it does! So we evaluate 1 in F4 to get a new integer object, which we return.

But this was just the return from our most recent function call! Let's remember how we got here. We were evaluating n * factorial(n-1) in F3. So now we can go back and finish that computation, taking the result of our recursive call (1) and multiplying it by 1 to get our result.

STEP 11

Notice that we're returning 1 from the function call that created F3. But how did we get there? We were evaluating n * factorial(n-1) in F2! So we can take this result (1) and combine it with the 2 from before to get the return value from F2!

STEP 12
And now that we know this value, we can combine it with our 3 to get the overall result from F1 (from our original function call).

STEP 13
And, finally, we have found the result of our original call! And the very last step is to clean up F1.

STEP 14
This was quite a process, but hopefully it was helpful to walk through the steps here to see how things were working themselves out as this program ran. Of course, if you have questions about this process, please don't hesitate to ask them!

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

As a follow-on question, with factorial written as above, how many total frames (other than the global frame and the built-ins) are created when we call factorial(7)?

3) Recursion in the Wild§

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.

4) Summing a List§

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

4.1) Aside: Doctest§

We're not done with sum_list yet, but let's take a moment to write some tests and see another useful Python tool that may not be familiar to you. There's a module built into Python called doctest, which lets us embed simple test cases inside the docstring of a function. The tests are formatted as if they were typed at the Python prompt, using >>> to indicate what should be typed, followed by what the expected output should be:

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

This is already helpful, because it gives examples of using the function to a human reading the docstring. But doctest goes a step further by automatically extracting these test cases and running them as automatic tests. If you call doctest.testmod(), e.g. in the main block of your file, then it will run all the docstring tests it can find in that file:

... # definition of sum_list

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

Now running the whole file will invoke all the docstring tests, and we'll see that it passed:

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

It's a good idea include verbose=True as a parameter to testmod() -- otherwise, when all the tests pass, as in this case, doctest will simply succeed silently.

We can put as many doctests as we want into a docstring, so let's add another, which looks at what happens when we sum an empty list:

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

Trying:
    sum_list([1,2,3,4,5])
Expecting:
    15
ok
Trying:
    sum_list([])
Expecting:
    0
**********************************************************************
File "/Users/rcm/6.101/fall22/web/readings/recursion/sum_list.py", line 8, in __main__.sum_list
Failed example:
    sum_list([])
Exception raised:
    Traceback (most recent call last):
      File "/Users/rcm/.pyenv/versions/3.10.1/lib/python3.10/doctest.py", line 1346, in __run
        exec(compile(example.source, filename, "single",
      File "<doctest __main__.sum_list[1]>", line 1, in <module>
        sum_list([])
      File "/Users/rcm/6.101/fall22/web/readings/recursion/sum_list.py", line 14, in sum_list
        return x[0] + sum_list(x[1:])
    IndexError: list index out of range
**********************************************************************
1 passed and 1 failed.
***Test Failed*** 1 failures.

Oops! We have a failure. Can you see why it's going wrong? We'll see how to fix it in the next section.

One big caveat about doctest: it works by checking printed output, not by using == to compare the expected value with the actual value (which is what we do with assert in other kinds of tests we write). This has two unfortunate effects:

• if you put any print statements into your code to debug it, those prints will cause doctests to fail, because the docstring won't mention them as expected output. You have to remove or comment out all your debugging prints in order for the test to pass again.
• if there is any harmless variation in the output -- for example, the order in which a set or dictionary is printed -- then the test will fail, even if the set or dictionary is actually correct. We'll see one way to deal with this problem below.

That said, the convenience and understandability of having executable test cases right in a function's documentation can be a big win.

4.2) Getting the Base Cases Right§

Let's add a base case to deal with the empty list:

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

Now the code works, but if we reflect on it a little more, do we need both of these base cases? No! Now that we handle the length-0 list correctly, the length-1 base case is redundant with the recursive case. To see this more clearly, we can imagine having base cases for length-2, length-3, and so forth:

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

This code is not DRY (that is, it doesn't follow the principle of "don't repeat yourself"). The more redundant base cases you have, the more places there are for bugs to hide. (In fact there is a bug hiding in this example -- can you see it?)

So let's simplify to the fewest base cases and recursive cases we can manage with. We'll also write the empty-list test slightly more pythonically, since empty lists are falsy:

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

5) Summing a Nested List§

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

6) Choosing the Right Decomposition For a Problem§

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

Fill in the blank for this additional doctest for subsequences:

>>> subsequences(["x"])
__________

6.1) Aside: Canonical Output For Doctest§

Oops, before we work on implementing subsequences recursively, let's fix a problem with these doctests. Doctest works by matching the actual printed output against what we wrote in the doctest, but a set can print in any order. All of the following would actually be the same set:

{(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)}

... but only the first one would pass the doctest as we wrote it. So let's make a small change to improve the test by putting its output in a canonical form, in this case putting the tuples in sorted order. To do that, we'll have to print a list instead of a set:

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

Note that tuples are sorted lexicographically, i.e. by comparing one element at a time and stopping as soon as an element is different or one tuple runs out of elements (in which case the shorter tuple wins).

This example shows that a doctest doesn't have to be just a single call to the function -- it can do some other work as well, in order to make the test more tolerant of harmless variation.

But keep in mind that even though our doctest converts the set into a sorted list for the sake of consistent printing, the subsequences function itself is still just working with sets.

Fill in the blank for this improved doctest for subsequences:

>>> list(sorted(subsequences(["x"])))
__________

6.2) One Way to Do Subsequences§

The subsequences problem lends itself to an elegant recursive decomposition. Consider the first element of seq. We can form one set of subsequences that skip that element, and we can form another set of subsequences that include that element, using the subsequences of the remaining elements. Those two sets generate all possible subsequences for the original input:

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

What is the first recursive call made by subsequences([4,2,3])? Write your answer as the Python list that is passed as its parameter.

What is the return value of that first recursive call? Write your answer as a Python expression.

We might try to write the computation of the result set more compactly using set comprehensions, like this:

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

Which of the following describes the effect of this code change?

It contains a Python syntax error.
It will raise an exception when it runs.
It will make far more recursive calls than before.
It will return the wrong answer because the result is being created in a different order.
It will work as expected in about the same time.

7) Recursive Helper Functions§

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

8) Choosing the Right Recursive Subproblem§

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]

Which of the following can be substituted for the IS_BASE_CASE and BASE_CASE to make the code correct? It may help to think through the doctest cases shown in the docstring.

elif n == 0:
    return "0"

elif n == 0:
    return ""

elif n < b:
    return str(n)

elif n < b:
    return digits[n]

9) Summary§

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.