⬇️The Use It/Lose It Principle

Making tree recursion intuitive.

If you've been using this book as a side-along to lectures and the class, then you most certainly know the following question: count_partitions. If you're like most 61A students, you dread this question.

The function returns the number of different partitions of n using parts up to m.

def count_partitions(n, m):
    """
    Count the ways to partition n using parts up to m.
    """
    # TODO

Before we dive into code, let's talk about the approach we take to solve this question on a higher level with an example. Consider the questions count_partitions(6, 4). This returns 9 — that is, there are 9 ways to count up to 6 using the numbers 1, 2, 3, and 4. Let's enumerate them:

6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 3
6 = 1 + 1 + 4
6 = 1 + 1 + 2 + 2
6 = 1 + 2 + 2 + 3
6 = 2 + 2 + 2
6 = 2 + 4
6 = 3 + 3

A couple things to note:

1. Order doesn't matter. 4+2 and 2+4 are equivalent for this question.

2. Notice how I've formatted the various ways to sum up to 6. First, we use all ones. Then, we use all ones and a two. Then, all ones and a three. Then, all ones and a four. Then, ones and twos. And so on and so forth. This is very much on purpose, and we will use this fact to develop our approach to solve this question.

If you had attempted to enumerate these ways with me, perhaps you did it intuitively — writing combinations that made sense until we'd exhausted all possibilities. Perhaps you did it the way I did — using as much of a number as possible before adding the next one. Now, it is incumbent upon us to ask: how would a computer go about thinking about how to count these?

If we can figure out an answer to this question, we have essentially mastered all questions that follow this pattern.

Imagine that the computer does it inversely to how we did it above — it uses the largest number as much as possible before adding the next smaller number. This means it will make 4+2 before 4+1+1 before3+3. Larger numbers first.

With this in mind, the big picture idea is this: At any given stage, the question can use the current value of m to try to count up to n, or it can discard m and go to the next value of m. Visualized, this looks something like this:

Count Partitions, Visualized.

Notice how, at any given point, the computer can use the value of m or lose the value of m. I call this this Use It/Lose It Principle. So, how does the computer decide which one to do. Here's the last trick: the computer doesn't pick which one to do, but rather does both of them.

With all of this in mind, let's write this out in code! We'll skip our base cases for now and just write the recursive case.

def count_partitions(n, m):
    """
    Count the ways to partition n using parts up to m.
    """
    # Base Cases
    # TODO
    
    # Recursive Case
    use_it = count_partitions(n-m, m) # Number of ways to count n using m
    lose_it = count_partitions(n, m-1) # Number of ways to count n without using m
    return use_it + lose_it # Total number of ways 

Yet another way of thinking about this is to split the question into two universes: a universe in which m is used in the counting of n and one in which m is not used in the counting of n. These two universes are mutually exclusive by definition, thus, the number of ways each of the recursive calls return have no overlap. Thus, we can add them together to count the total ways.

Let's wrap this question by establishing our base cases. Look at our visualization above — when does our tree stop. There are three cases: if n<m, if n==m and if m==0. Let's put these in:

def count_partitions(n, m):
    """
    Count the ways to partition n using parts up to m.
    """
    # Base Cases
    if n < m: # Cannot get to n anymore
        return 0
    if n == m: # Got to n
        return 1
    if m == 0: # Cannot get to n anymore
        return 0
    
    else:
        # Recursive Case
        use_it = count_partitions(n-m, m) # Number of ways to count n using m
        lose_it = count_partitions(n, m-1) # Number of ways to count n without using m
        return use_it + lose_it # Total number of ways  

And we're done! Note this question in the CS61A Textbook. The base cases are different. This is done on purpose to introduce to you the idea that there is no "right" base or recursive case: only what works and what doesn't. As long as you pass the doctests, your approach is correct.