A Good Use Case For Recursion

Today I am going to tackle a monster. That monster is recursion and I want to not only tackle it, but put it to good use. Hello! My name is James and I am an aspiring coder hoping to share some of the insight I have acquired from my own coding journey with anyone who's interested! Recursion can be a tricky coding practice so we'll start by exploring what it is and when we should use it. Then we'll wrap up with a good use case for recursion: traversing a tree.

Recursion seems to be big and scary when we first encounter it. So, like any monster we need to take down, let's give it a name and a definition before our imagination over-inflates the situation. Recursion is a function that calls itself. That's it. A function that contains a function call of itself inside the function body.

Thinking this through there is an obvious issue that will quickly arise. When does the recursive function stop calling itself? Won't this create an infinite loop? It absolutely does if we don't do something about it. A recursive function calls itself with what we will call the "recursive case" and it stops calling itself once it has reached its "base case."

This is a very simple recursive function that will find the result of a given number raised to the power of a given exponent. Inside of our function code block we begin with our base case. That is a good place to start so that we don't create an infinite loop. Then we have our recursive case that calls the function inside of itself. Once the function calls resolve we end up with the given number multiplying itself the n number of times.

This is a cute little function that properly uses recursion but what about on a larger scale? When else should we use recursion in our code? A few suggestions quickly come to mind. We should aim to use recursion when:

-we find ourselves writing the same code over and over
-when we want to make our code shorter/ easier read
-when the only solution is recursion

Let's focus on a situation that addresses all three of these opportunities: using recursion to traverse a tree data structure. Trees are data structures that are made up of nodes, in our example each node will be an object and has the capability of having 'children' (other nodes that are nested inside of it). Let's say that we want to get a specific value from a tree that has child nodes 4 levels deep. We would have to iterate over the great-great grandparent node, then the grandparents, then the parents and then the children to make sure that we touched on each node.

A simpler approach would be: examining the first node (great-great-grandparent) and then if it has children lets examine them by calling the same function on each of them. This will repeat until every existing child node has been passed through our function recursively!

I love ice cream. I even like coming up with my own combinations of ingredients in my ice cream. So I'm going to harness this love for ice cream to make a tree data structure consisting of objects that are flavors of ice cream and have children of other flavors of ice cream.

As you can see, each ice cream flavor has a deliciousness rating. This will be a number between 1 and 10 that shows how much I enjoy eating that particular flavor of ice cream. Here is what our tree looks like:

Notice the progression of flavors as it goes deeper into the tree, each level has more ingredients than the parent flavor. My tree has a clear sense of organize to it, but I have another problem now. I I want to go to the store and buy my favorite ice creams based off of how delicious they are (i.e. their deliciousness value) and that is NOT how my tree is organized. Here is how I rated them:

These numbers are all over the place because that is not how I originally constructed my tree. No problem, I will iterate over the entire tree and return only the ice cream flavors I rated as a 7 or higher, and to do so, I'll utilize the power of recursion.

Our recursive function only has two main parts to it and we actually combined the base case and recursive case to be in the same line. This function will examine the first node we pass in, and then simply call the same function on its children. If a flavor of ice cream meets our desired rating then we will return it in an array concatenated with all of the other flavors that meet our deliciousness rating requirements. Here are the results:

We have done it. We tackled the monster named Recursion and applied its power to solve our problem showing us which ice creams we would like to purchase.

Recursion is a function that calls itself. We can wield this simple and yet awesome coding tactic to keep from repeating ourself in our code, to clean up and make our code more aesthetically pleasing, and to traverse data structures like trees which will give us access to each node within them. Nothing to be afraid of here, try it out for yourself!