The Official Recursion Cheat Sheet

Given the amount of material I already have on recursion on this site, you’d think I’d be done talking about it. Unfortunately, you’d be wrong. As I hinted in the five tips article, there are ways to solve recursion problems without having a deep understanding of how recursion works. That’s the topic of today’s article!

Table of Contents

Cheat Sheet

There are a lot of different ways to organize a cheat sheet. My approach in this article is to organize the cheat sheet by types of recursion problems. If you weren’t aware there were types, this cheat sheet will definitely help you out!

With that said, I don’t plan to cover what recursion is or how it works. If that’s a topic you’re interested in, feel free to check out my Yet Another Way to Learn Recursion article.

Recursion on Sequence Data

In general, the way you solve recursion problems depends on the type of data you’re using. For example, you might be asked to perform recursion on a sequence data type. For our purposes, I define sequence data as any data that is linear (e.g., strings, arrays, queues, etc.). With these data types, recursion doesn’t exactly come naturally. Instead, our tendency is to solve problems like these using loops, but it’s possible to use recursion. Here’s the trick:

1. Make the sequence smaller by removing an element
2. If the subsequence is not empty, make a recursive call on the subsequence
3. If needed, restore the sequence by adding the missing element back

Here’s an example:

def length(s: str) -> int:
    size = 1
    if not s:
        size = 0
    else:
        size += length(s[1:])
    return size

In this example, we have a function that computes the length of the string. To do that, we assume that shrinking the string will remove a character. If not, then the string must be empty. In that case, we set size to zero. Otherwise, we remove the first character of the string and place the substring in a recursive call. In the end, we return the size. Luckily, because strings are immutable, we don’t have to restore them.

Let’s try another example! This time we want to compute the length of an integer. It’s easier than you’d think:

def length(num: int) -> int:
    size = 1
    if num > 9:
        size += length(num / 10)
    return size

In this example, our solution even closer mirrors the suggested process. Specifically, we assume a number can be no less than one digit. I think that’s a safe assumption. If it’s greater than one digit, we should shrink that number and call recursion. With numbers, we can shrink them by removing a digit. To remove a digit, all we have to do is divide by 10. Therefore, the recursive method computes the length of a number by the number of times you can divide it by 10 before it becomes zero. How cool is that?

Now, some problems on sequences are going to be harder, but the process is generally the same. If you know to shrink the sequence before the recursive call, you’re probably 80% of the way to solving the problem (unless you try to implement something like divide by 2).

Recursion on Tree Data

If sequence data lends it self better to loops, then there must be a data type that lends itself more to recursion. Fortunately, there is! Introducing the tree data type. In short, trees are a recursive data structure which basically means that trees are made of trees. Some examples of trees in the real world is your file system (i.e., folders in folders) and onions (onions inside onions). Therefore, recursion works because you can call the same function on subtrees without worry. Here’s how you do it:

1. Perform whatever calculation you need to on your root node
2. Call recursion on the subtrees.
3. Profit

Let’s take a look at another example:

def size(t) -> int:
    count = 1
    for child in t:
        count += size(child)
    return count

In this example, we have some tree object, t. The smallest possible tree we can have is a single node, so we assume count is one. Then, we iterate over all of the children of the tree, asking them for their size. When the subtrees report back, we add their result into count. The final count should be the total size of the tree.

Of course, these types of problems can be more complex. For example, imagine we had a boolean expression tree. In this tree, we would have to be able to handle the boolean operators (i.e., AND, OR, and NOT). Here’s what that might look like:

def eval(t) -> bool:
    result = false
    if t.value in [True, False]:
        result = t.value
    else:
        if t.value == AND:
            result = eval(t[0]) and eval(t[1])
        elif t.value == OR:
            result = eval(t[0]) or eval(t[0])
        else:
            result = not eval(t[0])
    return result

While this solution is a lot more complex, the premise remains the same. In this case, the smallest problem is a single node holding a value of True or False. If it’s not one of these values, we know we don’t have the smallest case, so we attempt to process one of the other three types of nodes (i.e., AND, OR, or NOT). Depending on the node, we know what the child structure should look like, so we make our recursive calls on the appropriate children. With that said, that’s all I want to cover with this. Let’s wrap things up!

Other Types of Recursion

In general, I don’t intend for this cheat sheet to be exhaustive. There are certainly recursion problems that don’t fit these two types. For example, there are a lot of mathematical expressions that can be written using recursion, like power, which look more like this:

def power(base: int, exponent: int) -> int:
    result = base
    if exponent == 0:
        result = 1
    else:
        result *= power(base, exponent - 1)
    return result

Another topic to consider is recursive functions with no return type (i.e., the value carries through a mutable variable). I’ll leave that for you to think about (or more likely I’ll just write about it later).

Finally, I also think it’s worth mentioning that recursion can be expensive, so we have to concern ourselves with efficiency. If that’s a topic you’re interested in, I recommend checking out the topic of dynamic programming.

With that said, that’s all I have time to cover today. If you liked this and want more like it, feel free to check out one of these related articles:

• 5 Tips for Making Sense of Recursion
• Yet Another Way to Learn Recursion

Otherwise, I’d love for you to head over to my list of ways to grow the site. If not, no worries! Take care.

Coding Tangents (43 Articles)—Series Navigation

As a lifelong learner and aspiring teacher, I find that not all subjects carry the same weight. As a result, some topics can fall through the cracks due to time constraints or other commitments. Personally, I find these lost artifacts to be quite fun to discuss. That’s why I’ve decided to launch a whole series to do just that. Welcome to Coding Tangents, a collection of articles that tackle the edge case topics of software development.

In this series, I’ll be tackling topics that I feel many of my own students have been curious about but never really got the chance to explore. In many cases, these are subjects that I think deserve more exposure in the classroom. For instance, did you ever receive a formal explanation of access modifiers? How about package management? Version control?

In some cases, students are forced to learn these subjects on their own. Naturally, this forms a breeding ground for misconceptions which are made popular in online forums like Stack Overflow and Reddit. With this series, I’m hoping to get back to the basics where these subjects can be tackled in their entirety.

← Previous Post: [#28] [#30]: Next Post →