Programming with JS: Recursion

Understanding data structures, algorithms and basic programming concepts is essential for one to become a better developer. Nowadays most of those problems are solved using modern tools and libraries, but having deeper knowledge in that area will definitely broaden your perspective of software development.

Personally, for me it was pretty hard to get a grasp on some of those concepts, because I was not using them in my day-to-day work. I’m writing this series to improve my own understandings on those topics and help other people like me.

What is Recursion

Recursion is one of the main concepts in programming. You have undoubtedly seen that scary word in algorithm books and articles followed by examples of calculating the Fibonacci numbers or something in those lines. As a web developer you’re probably not using the Fibonacci sequence in your every day coding assignments or implementing sorting algorithms — at least I’m not.

When I first started reading about recursion I was having problems understanding where exactly this could be useful. I understood the benefits of the approach and it’s applications in certain algorithms but it was hard to find situations in which I would prefer the recursive over the iterative approach.

Before you continue — this article expects you to have a basic understanding of what recursion is and basic understanding of the JavaScript language. So, let’s start with a definition that I find easy to understand:

Recursion is when a functions calls itself until it reaches a certain state

Let’s split this in two parts and talk about each one of them. A function calling itself means that inside the body of the function we will have a call to the same function — inception, right? The first time you see a recursive function it will probably break your understanding of code execution, but this is absolutely normal.

When we use recursion it will go on until it reaches a certain desired state. In some cases we must call the function a fixed amount of times. In other cases it will continue running until a conditional check tells it to stop. In both cases we must have a well-defined stop condition in order to prevent the recursion from running forever.

Applying Recursion

Definitions and explanations are not going to get us anywhere so let’s start with a practical example. We’ll be using recursion to illustrate how to order a list of categories into a tree-like hierarchy. Here are the categories that we get from a service. They have the name and their parent category:

Your task as a JavaScript developer is to arrange those categories in a tree-like structure so you can list them somewhere on the page. The first thing that can come to your mind is to use some nested loops, however this is not the most elegant approach. It will work for the time being, but you will depend on the structure remaining as it is right now and if in some point a child level is removed or added you will have to modify your code.

This is a perfect example of when using recursion can be a lot better than the normal iterative approach. We will start by creating a function, which will take two arguments — the array and the parent of the category we’re looking for. Keep in mind that we are not just accessing the categories from the global state, because we will be going through them recursively.

const arrangeCategories = (category, parent) => {let result = {}// function body herereturn result}

The Recursion Body

Next, we need to actually implement the recursion. What we’re aiming for is having an algorithm that does not depend on the level of nesting. Here’s the complete function that we will be using:

Let’s walk through what’s happening here.

1. On line 4 we filter through the categories and get only those with the correct parent (which will be null on the first call)
2. After we have the required categories, for each one of them we add them as a key on the results object and make a recursive call to find all of it’s child categories
3. Repeat the first steps

The Result

After applying the recursive function we achieve the following result:

All the categories are ordered creating a proper hierarchy that will be easier to loop through and list. Recursion is definitely a really broad topic and it is used to solve problems more difficult than the simple listing of unsorted categories, but this is a good place to start.

Thank you for the read, if you’re interested in JS related content I have a full series on core JS concepts in my profile!

Programming with JS:

Recursion: https://hackernoon.com/programming-with-js-recursion-31371e2bf808Merge Sort: https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0Binary Search: https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3Insertion Sort: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5