Recursion in Javascript

Have you ever found yourself needing to loop through a complex multidimensional object in JavaScript and didn't know how to do it? If this is the case, you should consider using Google as a powerful tool to find a solution. However, since you're here, if you keep reading, you may find an elegant solution to this problem.

Let's start by taking the following tree as an example.

const mySuperComplexTree = {
  name: "root",
  children: [
    {
      name: "child-1",
      children: [
        {
          name: "child-1-1",
          children: [
            {
              name: "child-1-1-1",
              children: []
            }
          ]
        }
      ]
    },
    {
      name: "child-2",
      children: []
    }
  ]
};

The problem: You have to print to the console each one of the node names, including the root.

The first time we come across these kinds of problems, we tend to get ourselves led by the Dunning-Kruger effect and think that this can be solved with a simple for loop. The short answer is yes... But also, no, that's not always the best approach.

Let's see what happens when we follow this approach:

console.log(mySuperComplexTree.name);
for (const node of mySuperComplexTree.children) {
  console.log(node.name);
  for (const node2 of node.children) {
    console.log(node2.name);
    for (const node3 of node2.children) {
      console.log(node3.name);
    }
  }
}

// Output:
// root
// child-1
// child-1-1
// child-1-1-1
// child-2

As you might see, even though it worked, there are several issues with this solution:

1. First of all, it's not easy to read. Nobody wants to see a bunch of nested loops on their code and you're a team player, right?
2. What will happen if this tree is supposed to change during runtime? The current implementation is not dynamic, so you must modify the code and add more nested loops manually. This can make the code harder to read and less maintainable.

Here's where recursion comes in handy.

So, what's a recursive function anyway?

It is a function that calls itself during its execution. This characteristic allows it to be used to solve problems that can be broken down into smaller and simpler sub-problems that are identical to the overall problem.

An easy way to visualize this would be a countdown function using recursion. Let's see.

function countDownFrom(n) {
  if (n < 0) return;
  console.log(n);
  countDownFrom(n - 1);
}
countDownFrom(10);

In this example, the countDownFrom function prints a number, then calls itself (recursion) with the number you passed, minus one, repeating this process until it reaches a base case (in this case, when n is less than 0).

As you can see, it's basically a loop but simpler and more elegant.

Let's go back to our tree object.

Our initial problem is that we need to print all the node names of the tree, and we are going to use recursion to solve it because we noticed our tree has a constant structure where each node has a name property (the string we are going to print), and a children property (an array of nodes).

So, our function needs to receive a node and print its name, then as all of the children are similar, we can loop one time through the children and just call the same function passing the child. This will receive a doe, print its name a repeat the process.

function printNodeNames(tree) {
  console.log(tree.name);
  for (const node of tree.children) {
    printNodeNames(node);
  }
}

printNodeNames(mySuperComplexTree);

// Output:
// root
// child-1
// child-1-1
// child-1-1-1
// child-2

As you can see, the printNodeNames function solves our initial problem.

It starts by printing the name of the current node (which is passed as an argument). Then, it loops through the children's array of the current node, and for each child node, it calls itself (recursion, again), passing the child node as the new argument. This process continues until it has printed all node names in the tree. Just what we said we needed.

This function demonstrates a common pattern for traversing a tree structure: processing the current node (in this case, printing its name), then recursively processing all child nodes.

This technique is known as a depth-first traversal because it goes as deep as possible into the tree before backtracking.

Why to use recursion

If for some reason, you're not convinced yet about using recursive functions, I'm going to leave you with four reasons why recursive functions are so useful.

1. Simplicity: Recursion is often more straightforward to understand than its iterative counterparts (for, while, etc). They can turn complex tasks into much simpler ones.
2. Problem Solving: Some problems are inherently recursive, like tree traversals, Tower of Hanoi, etc. For such problems, it is easier to use a recursive function.
3. Divide and Conquer: Recursive functions allow you to break down larger problems into smaller, more manageable sub-problems. This is the basis of many efficient algorithms like merge sort and quick sort.
4. Less Code: Recursive functions can lead to less code. Ok, shorter code doesn't necessarily mean better, but it can make the code more readable.

In conclusion, Recursion is not only an elegant solution for some problems but it is a powerful and useful tool for tasks that can be broken down into smaller ones, such as traversing a tree or sorting a list.

Their key components are the base case (the condition under which the function stops calling itself) and the recursive case (the part of the function that calls itself).

However, they can be more difficult to understand and debug than iterative solutions, and they can also lead to performance issues such as stack overflow if not implemented carefully. Therefore, it's important to use recursion judiciously and ensure that the base case is always reachable.

I hope you found this post useful and please let me know if you have used recursive functions before for a real-life scenario.