Numbers All The Way Down

Video: Youtube Video (apologies for the quiet audio)

In this post, we’ll use the computer science concept of recursion to determine, How many swings does it take to kill a Minecraft slime?

This article is intended for readers who have a basic understanding of the computer science topics of if/else statements and functions. These concepts are critical to understanding the following example. It also helps to have a basic understanding of Minecraft combat mechanics.

The goal of this post is to explain the, often confusing, topic of recursion using a modified example of the process of killing a Minecraft slime. Typically, teachers will use examples like the Fibonacci sequence and the Towers of Hanoi to explain recursion. However, students often find these examples confusing because the underlying concepts are foreign to their prior experiences. My hope is that using the more relatable example of killing a Minecraft slime will make it easier for students to grasp the basics of recursion.

By the end of this post, the reader should have a basic understanding of the methodology underlying recursion and be able to generalize the concept to other topics beyond that of killing a Minecraft slime.

What is recursion

Recursion is a method/tool in computer science used for breaking down a complex problem into smaller, repeatable parts/cases and a base case. A base case is the term used to refer to the final/solved state of the complex problem. With recursion, the main idea is that you can repeat the smaller cases until you reach the base case, at which point you aggregate the information you gathered at each of the smaller steps to arrive at your desired conclusion. Just having a definition of recursion often isn’t helpful to developing a meaningful understanding of the concept. As a result, any introductory lesson to recursion is incomplete without examples walking students through the basic though patterns of applying recursion to a problem.

The first step of solving a problem with recursion is to determine the problem statement. A problem statement outlines the problem that we want to solve, and, when talking about this from a programming perspective, is often used to help name the function. For this example, the problem statement will be How many steps does it take you to get from one side of the room to the other?

With this example (and the Minecraft slime example) I will provide interspersed pseudocode to make it easier to understand how you go from thinking about a problem recursively to actually coding it. Right now, we just have the beginnings of a function that will help us determine how many steps we need to get to the other side of the room.

Step two is to determine a base case. Useful questions to ask to determine a base case are, when will I know that I’ve answered my question or when is my problem solved. Often, you’ll find that a good, well-defined problem statement will have the base case already included in it, as is the case in this example. Explicitly put, the base case is reaching the other side of the room. This is the point where you don’t have to take any more steps.

With our base case in hand, we now need to determine the small, repeatable action that we can take to solve our problem. In this case, the repeatable action is one step. You just need to keep count as you put one foot in front of the other. In pseudocode, it would look something like this.

That last line of pseudocode translates into take a single step, and then, from that new position, determine how many steps it takes to get to the other side of the room (represented as the call to steps_to_other_side_of_room()). After taking enough steps, you’ll eventually get to the point when you’ve reached the other side of the room, a.k.a your base case. Then, like a zipper, every call you made to steps_to_other_side_of_room() return and you end up with an equivalent to 1+1+1+1+....+0. Each +1 is a step that you took on the way to reaching the base case, and when you add all those steps up, you’ll have the answer for the total number of steps it took you to get to the other side of the room.

Recursion is a difficult topic, and don’t feel disheartened if you didn’t completely understand the above example. Often, students have to go through multiple examples to get to a point where recursion starts to make more sense. So, for our next example, we are going to kill a Minecraft slime using recursion.

Killing a slime: Problem Statement

As always, the first step we need to take is to determine the problem statement. In this case, we want to know, How many swings will it take to kill a Minecraft Slime? If you replace swings with steps, and kill a Minecraft slime with other side of room, you’ll realize that we are dealing with a very similar example to the one that we just reviewed. That’s because both of these problems fall into a similar category of problem that is very well suited for recursion. Often, these problems take the form of How many X does it take to do Y? As we continue with our Minecraft slime example, we’ll continue to use pseudocode to illustrate exactly what is going on and simulate what an actual solution might look like if you were to actually write out the code in a programming language like Python.

Caveats before getting into the tutorial more

This section will briefly get into Minecraft mechanics that are ignored in the example so that people more familiar with the game aren’t confused when they are omitted.

At the beginning of this example, we will not account for the fact that the slime splits when damaged enough. This will be reintroduced later in the explanation.

This example does not specifically consider any weapons that the player might be holding, which can change the player’s damage output and kill the slimes faster. If you want, you can append your weapon of choice to the question above as follows How many swings will it take to kill a Minecraft Slime with a diamond axe?. All of the principles for understanding recursion outlined below can be applied in the same way no matter the weapon the player has equipped.

This example also doesn’t account for more complicated game mechanics, such as sweeping edge. It is not so easy to clearly quantify these mechanics in this base level introduction to recursion. Sweeping edge is also specifically ignored since players often have a hard time consistently applying and keeping track of damage applied with it.

For the sake of this tutorial, all swings taken target only one slime and only deal damage to that singular slime.

Base case (AKA The Success Case)

Before we continue, I want you to take a second and think about what the base case should be. Consider the steps to the other side of the room example and the problem statement that has already been outlined above. Then, once you’ve thought about it and think you have a solution, read on to the next paragraph.

The correct answer for the base case is any question similar to Is the slime dead?. If you had some difficulty thinking about the base case, it might also help to think of the base case as the success case. In other words, we want to know when we need to stop looking for an answer. If the slime is dead, we no longer have to keep swinging and counting to get our result. Zero is returned in the pseudocode as the explicit representation of the fact that no further swings need to be taken.

Take a swing

With a base case in hand, we now need to determine our small, repeatable step. And, as you might have guessed, that small, repeatable step is taking a swing at the slime.

Let’s break down the line we just added to our pseudocode above. The 1 refers to the swing that we just took. Then, after we’ve taken that swing, we apply the function. In English, this would translate into, now that I’ve taken a swing, how many more swings will it take to kill a slime. Eventually, you’ll reach the case where the slime_is_dead and then you’ll have your answer. Up until now, this is exactly the same problem as the earlier mentioned, how many steps does it take to cross a room.

The slime splits

Readers that have played Minecraft know that this isn’t the complete picture when it comes to killing a slime. This is because, after taking enough damage the slime splits into 2-4 smaller slimes. And, a slime can’t be considered completely killed until after all of the smaller slimes have been killed as well. So far, our code has only considered a single slime (without including the offshoots). However, we can use what we have and generalize it slightly to suit our needs now that we are going to incorporate the fact that the slime splits.

In recursion, there is a concept of a case. A case is the formal word for the small, repeatable step you’re already familiar with. However, there is no rule that says recursion can only have one case. So, to account for the fact that more slimes are generated when a larger slime splits, we need to add a case that allows for that.

Now, we have a case that handles if a larger slime splits into two smaller slimes. With two slimes in focus we defer taking a swing at either of the slime immediately, and instead ask our recursive function “tell me how many swings it takes to kill slime 1, tell me how many swings it takes to kill slime 2, and then add those two numbers together.” Just like that, we’ve simplified our problem back to killing one slime at a time. We can further extrapolate this example of 2 slimes being split off into the cases for 3 and 4 slimes being split off. The pseudocode for that is right below, but I’d first like you to take a moment to think about how you expect those cases to look like.

In the pseudocode above, we add two more cases for the slime splitting into 3 and 4 slimes and follow the same pattern that we outlined for if the slime split into 2 slimes (defer the swing and just focus on killing one at a time). Eventually, you take enough swings and all the slimes are gone. Then, same as before, you add all the +1 values that you’ve generated by taking a swing and arrive at the final result of just how many swings it takes to kill a minecraft slime.

The best part of this approach is that, even if the slime is large enough to split multiple times, you’re still able to apply the above solution to get the answer to our original question of How many swings does it take to kill a Minecraft slime?