An Easy Way to Understand Recursion in JavaScript

What you see on the picture above is a Mandelbrot set. Arguably the most famous fractal. Fractals are a set of infinitely complex geometric shapes and they have a special trait. On different magnification levels, they appear the same.

So what do fractals and recursion have in common? They keep repeating themselves in a self-similar way.

Get access to 300+ webtips 💌

Level up your skills and master the art of frontend development with bite-sized tutorials.

We don't spam. Unsubscribe anytime.

Get Access to Webtips

---

What Is Recursion In a Sentence?#

Recursion happens when a function calls itself.

That’s all there is to it. You may have also heard the famous phrase by Stephen Hawking:

To understand recursion, one must first understand recursion.

While it is certainly a clever joke about recursion, we can truly understand it by using it. So how does it translate into practice? Let’s see some practical examples.

First of all, how do we know when to use a loop and when to use a recursive function? While loops have a definitive end to their sequence, there is no sequential end for recursions. Simply put, if you don’t know the number of times you need to loop, you’ll need to use recursion. This is why it’s so important to have a stop condition. Otherwise, you’ll end up creating an infinite loop.

And what are some use-cases of recursion? Think of cascading menus where you can have submenus indefinitely. Another common use case would be to generate file trees. We can also include here generating hierarchies, networks or graphs.

To make it easy to understand, let’s start with the most basic scenario, counting down from a given number.

Imagine we have to print numbers to the console from 100.

We can do this with a simple loop but since we’re talking about recursion, we will go that way. Let’s inspect the following function:

const countDown = num => {
    if (num > 0) {
        console.log(num);
        countDown(num - 1);
    }
};

This function keeps calling itself until the passed number reaches 0. You’ve just created your very first recursive function! What happens if we don’t have the if statement? The function will keep calling itself infinitely, until this happens:

It reaches the browser’s maximum stack size which prevents it from running forever. Otherwise, we would quickly run out of memory. So we have to be very thoughtful about defining exit conditions for recursive functions. Now let’s see a little bit more complicated, but practical example.

Say you are building an app where you want to generate a file tree object from a real directory structure. Like the one below:

Each directory should be an object, containing everything in itself. If we hit a file, we can store its size as the value.

Start by creating a new file called recursion.js in the root directory. We will need to import the fs module first. Let’s start with the end in mind and see what we want to have. We want to have a function that returns a file tree object. This is what we will write into a JSON file.

const fs = require('fs');

const getTree = folder => { ... }

fs.writeFileSync('tree.json', JSON.stringify(getTree('recursion')));

So we need to implement the getTree function. It accepts a folder that we want to traverse. Let’s add some checks first.

const getTree = folder => {
    if (!fs.existsSync(folder)) {
        return null;
    }
    
    const fileTree = {};
    
    return fileTree;
}

First, we need to make sure we are dealing with a file or folder that exists. Otherwise, there’s no point in continuing. Then we want to populate the fileTree variable which we will return at the end. We can start by taking one of two routes:

• We are dealing with a directory
• We are dealing with a file

const fileTree = {};
const isDirectory = fs.statSync(folder).isDirectory();

if (isDirectory) {
    ...
} else {
    fileTree[folder] = fs.statSync(folder).size;
}

return fileTree;

If we are dealing with a file, we can assign the size to a new node, named after the passed parameter. Otherwise, we are in a directory. This means we need to call the function recursively, since we won’t be able to tell how many subfolders there are.

if (isDirectory) {
    const files = fs.readdirSync(folder);

    files.forEach(file => {
        const isSubDirectory = fs.statSync(`${folder}/${file}`).isDirectory();

        if (isSubDirectory) {
            fileTree[file] = getTree(`${folder}/${file}`);
        } else {
            fileTree[file] = fs.statSync(`${folder}/${file}`).size;
        }
    });
} 

This leaves us with the above implementation. For each file in the directory, we want to check if it’s a subfolder. Then we can call the function with a new path. When we hit line:8, we jump into a new folder and execute the same set of steps. If that folder has another subfolder, we do the same. And so on. Since the function returns a fileTree object at the end, we can assign its value back to fileTree[file].

At the very end, we run out of subfolders, this is our exit condition.

Go ahead and run this file with node recursion.js. A tree.json file should be generated at your root folder, containing an object representation of the folder structure.

Looking to improve your skills? Check out our interactive course to master JavaScript from start to finish.

Remove ads

---

Summary#

With that being said, you should have now mastered the art of recursions. Thank you for taking the time to read this article. I would like to close things off with a popular comic by Safely Endangered, which illustrates pretty well what happens when things go wrong in recursions: