Algorithms – The Renegade Coder

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! 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: Make the sequence smaller by removing an elementIf the subsequence is not empty, make a recursive call on the subsequenceIf 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: Perform whatever calculation you need to on your root nodeCall recursion on the subtrees.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 RecursionYet 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.