An introduction to recursion in Javascript

In nature, recursion indicates a pattern of self-similarity. It's observable in trees, plants, and even the feathers of some birds. In this article, we'll take a look at recursion in Javascript, how to implement it, and how it differs from other iterator functions.

How does recursion work?

In a nutshell, recursion in computer science describes a function call within its own definition. It's most commonly used to iterate through a list of similar items.

Let's look at a showcase. The following code function recursively prints each entry of a given array:

const items = ['one', 'two', 'three']

function printItemsRecursively(arrayOfItems, currentIndex) {
  // Condition to finish function execution at some point
  // In this case, we can use the array's length
  if(currentIndex >= arrayOfItems.length) {
    console.log("Finished iteration");
    return;
  }

  // Log the current item
  console.log(arrayOfItems[currentIndex]);

  // Recursive function call
  printItemsRecursively(arrayOfItems, currentIndex + 1);
}


printItemsRecursively(items, 0);

Similar functionality can also be achieved using for\ or while\ loops:

function printItemsForLoop(arrayOfItems) {
  const maxLength = arrayOfItems.length

  // Condition to finish function execution at some point
  for(let currentIndex = 0; currentIndex < maxLength; currentIndex++) {
    // Log the current item
    console.log(arrayOfItems[currentIndex]);
  }
}

function printItemsWhileLoop(arrayOfItems) {
  const maxLength = arrayOfItems.length;
  let currentIndex = 0;

  // Condition to finish function execution at some point
  while(currentIndex < maxLength) {

    // Log the current item
    console.log(arrayOfItems[currentIndex])

    // Increment index
    currentIndex++;
  }
}

printItemsForLoop(items)
printItemsWhileLoop(items)

At first glance, recursion looks more complex:

We must actively pass an additional argument into the function while the other loops handle the currentIndex\ internally.
We must implement an if-check to finish execution ourselves while the other loops have this check built-in.
If we forget to manually return in the if-check, we will always run into an infinity loop

Traversing tree structures

While these constraints might seem intimidating, they can prove helpful in tree structures. Tree structures are represented as nodes, where one node has one or many child nodes. You can find this structure in

Your project directory
Organizational charts with departments as the nodes
Generally speaking: Hierarchical data or information that is connected by references

The tree data structure

Let's look at an example. The following tree structure displays a hierarchy of employees with their superiors and associates.

The same structure can be expressed in JSON format or as a Javascript object:

const organisation = {
    name: 'John Doe',
    associates: [
        {
            name: 'Jane Doe',
            superior: 'John Doe',
            associates: [
                {
                    name: 'Mark Smith',
                    superior: 'Jane Doe',
                    associates: [
                        {
                            name: 'Marie Curie',
                            superior: 'Mark Smith',
                        },
                    ],
                },
                {
                    name: 'Andy Joy',
                    superior: 'Jane Doe',
                },
            ],
        },
        {
            name: 'Mycroft Holmes',
            superior: 'John Doe',
            associates: [
                {
                    name: 'Milly Smith',
                    superior: 'Mycroft Holmes',
                    associates: [
                        {
                            name: 'Max Doe',
                            superior: 'Milly Smith',
                        },
                        {
                            name: 'Linus White',
                            superior: 'Milly Smith',
                        },
                    ],
                },
            ],
        },
    ],
};

Moving through the tree's data

Our task now is the following:

Print each employee's data
Include the employee's superior
Include the level within the tree

For Linus White, the following statement would be correct:

Linus White is on level 3 of the tree. Their superior is Milly Smith.

Using recursion

With recursion, implementing these features is surprisingly straightforward:

function printEmployeeDataRecursive(employee, level) {
    // This is the lowest level of the tree
    // Print the message and return to prevent from infinity loops
    if (!employee.hasOwnProperty('associates')) {
        console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior}`);
        return;
    }

  // Print the superior, if maintained. 
    console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior || 'outside this structure'}`);

  // Print the count of their associates
    console.log(`${employee.name} has ${employee.associates.length} associate(s):`);

  // Apply printEmployeeData recursively to each associate
    employee.associates.forEach((associate) => printEmployeeDataRecursive(associate, level + 1));
}

Let's do it step by step, just to be sure we understand what's going on:

We check if the employee has any associates

If they don't, we're at the lowest level of the tree. We write out the employee's data, and that's it
If they do, we're not at the lowest level. We write out the employee's data, move to the next level, and start again

Note how we're using the additional complexity from earlier to our advantage here. It feels like the function keeps track of itself while moving through the tree's structure.

Using a queue

Let's look at an alternative without recursion. The most forward way I could come up with is to use a queue.

function printEmployeeDataQueue(employee, level) {
  const queue = [{employee: employee, level: level}];

  while (queue.length > 0) {
    const current = queue.shift();

    if (!current.employee.hasOwnProperty('associates')) {
      console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior}`);
      continue;
    }

    console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior || 'outside this structure'}`);

    console.log(`${current.employee.name} has ${current.employee.associates.length} associate(s):`);

    for (let associate of current.employee.associates) {
      queue.push({employee: associate, level: current.level + 1});
    }
  }
}

This approach is perfectly valid. Its only drawback is the overhead logic required to make it work:

A queue to process employee entries
A while - statement to check whether to run the procedure
A for-loop to add child nodes to the queue

You could also work your way through the tree nodes manually. But this would introduce additional, possibly unnecessary, and verbose code.

Digression: Without additional internal data structures

I was curious if there was a generic solution for this problem without recursion or additional data structures. Since I couldn't come up with one that does not make assumptions about the tree's depth, I asked ChatGPT.

ChatGPT: Rewrite the following function without using recursion, a queue or a stack:

I'll spare you the details (you can try to replicate this case yourself at https://chat.openai.com), but even ChatGPT could not provide a working solution to this problem that worked without recursion, a queue, or a stack.

Wrap up

Given the proper application, recursion is very elegant. While recursive functions introduce additional complexity, there are cases in which they come in handy. One example this article illustrated were tree-structures. Compared to a more classic iterator function, recursion introduced no internal processing logic, keeping the code clean and less verbose.

Sources and further reading

Full Code Reference

const organisation = {
    name: 'John Doe',
    associates: [
        {
            name: 'Jane Doe',
            superior: 'John Doe',
            associates: [
                {
                    name: 'Mark Smith',
                    superior: 'Jane Doe',
                    associates: [
                        {
                            name: 'Marie Curie',
                            superior: 'Mark Smith',
                        },
                    ],
                },
                {
                    name: 'Andy Joy',
                    superior: 'Jane Doe',
                },
            ],
        },
        {
            name: 'Mycroft Holmes',
            superior: 'John Doe',
            associates: [
                {
                    name: 'Milly Smith',
                    superior: 'Mycroft Holmes',
                    associates: [
                        {
                            name: 'Max Doe',
                            superior: 'Milly Smith',
                        },
                        {
                            name: 'Linus White',
                            superior: 'Milly Smith',
                        },
                    ],
                },
            ],
        },
    ],
};

function printEmployeeDataRecursive(employee, level) {
    // This is the lowest level of the tree
    // Print the message and return to prevent from infinity loops
    if (!employee.hasOwnProperty('associates')) {
        console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior}`);
        return;
    }

  // Print the superior, if maintained. 
    console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior || 'outside this structure'}`);

  // Print the count of their associates
    console.log(`${employee.name} has ${employee.associates.length} associate(s):`);

  // Apply printEmployeeData recursively to each associate
    employee.associates.forEach((associate) => printEmployeeDataRecursive(associate, level + 1));
};

function printEmployeeDataQueue(employee, level) {
  const queue = [{employee: employee, level: level}];

  while (queue.length > 0) {
    const current = queue.shift();

    if (!current.employee.hasOwnProperty('associates')) {
      console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior}`);
      continue;
    }

    console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior || 'outside this structure'}`);

    console.log(`${current.employee.name} has ${current.employee.associates.length} associate(s):`);

    for (let associate of current.employee.associates) {
      queue.push({employee: associate, level: current.level + 1});
    }
  }
}

Blog