An Easy Way to Understand Recursion in JavaScript

An Easy Way to Understand Recursion in JavaScript

Recursion demonstrated through practical example
Ferenc AlmasiLast updated 2021 November 11 • Read time 5 min read
Get your weekly dose of webtips
  • twitter
  • facebook
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.

Mandelbrot set on different magnification levels
Mandelbrot set on different magnification levels taken from Wikipedia

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


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.


Examples of Recursion

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.

Countdown

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

counting down with recursion

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:

Copied to clipboard! Playground
const countDown = num => {
    if (num > 0) {
        console.log(num);
        countDown(num - 1);
    }
};
recursion.js

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:

RangeError throws by Google Chrome

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.

Generating a file tree object

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

turning file tree into a json object with recursive function

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.

Copied to clipboard! Playground
const fs = require('fs');

const getTree = folder => { ... }

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

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

Copied to clipboard! Playground
const getTree = folder => {
    if (!fs.existsSync(folder)) {
        return null;
    }
    
    const fileTree = {};
    
    return fileTree;
}
recursion.js

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
Copied to clipboard! Playground
const fileTree = {};
const isDirectory = fs.statSync(folder).isDirectory();

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

return fileTree;
recursion.js

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.

Copied to clipboard! Playground
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;
        }
    });
} 
recursion.js

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.

running recursion.js to generate a file tree object

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.
Master JavaScriptinfo 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:

Recursion illustrated through a comic
  • twitter
  • facebook
JavaScript
Did you find this page helpful?
📚 More Webtips
Frontend Course Dashboard
Master the Art of Frontend
  • check Access 100+ interactive lessons
  • check Unlimited access to hundreds of tutorials
  • check Prepare for technical interviews
Become a Pro

Courses

Recommended

This site uses cookies We use cookies to understand visitors and create a better experience for you. By clicking on "Accept", you accept its use. To find out more, please see our privacy policy.