An Intro to Recursion with JavaScript

Recursion is a fundamental concept in computer science and programming that allows a function to call itself during its execution. It may seem like a simple concept, but the power of recursion lies in its ability to solve complex problems with elegant and efficient solutions.

The topic of recursion in programming can seem very daunting at first however, once you can follow a simple example, you can begin to see that it's not as bad as it seems. Recursion exists almost everywhere in common data structures. These data structures include trees, graphs, linked lists, heaps, stacks, and queues. In this blog, we will explore an introduction to using recursion in JavaScript and its many awesome benefits.

We're going to first begin by following a classic example of recursion, the mathematical factorial method. For example

!4 is the same as 4 * 3 * 2 * 1

This would be a perfect problem that can be solved by a recursive function. There are important factors to consider when constructing a recursive function, such as writing both the base case and the recursive case. Here are some tips to help you get started.

Base Case

Start by thinking about a condition when the function should stop calling itself and return a value. Then, think about the simplest possible input for the function, this will help to write your base case.

The base case should return a value that allows the function to complete the recursive process.

Test your function against the base case to confirm the desired outcome of your function.

Consider any edge cases and change your base case to handle them accordingly.

Recursive Case

The recursive case should take the larger problem and break it down into smaller sub-problems. It's important to identify the base case first so that you can figure out what the sub-problems will look like.

Determine the relationship between the larger problem and the smaller sub-problems. Once you've identified the sub-problems, you need to determine how they are related to the larger problem. This relationship will help you formulate the recursive case.

Make the recursive call for your recursive case. Every recursive call is the function calling itself within the function itself. Make sure to pass in the solution to the sub-problem that you've identified.

With the tips mentioned above, let's write our recursive factorial function!

function factorial(number) {
    // base case
  if (number === 0 || number === 1) return 1;

    // recursive case
  return number * factorial(number - 1);
}

Tracing the call stack we get something like this:

Great! now that you know the basics of recursion, let's apply it to something a little more useful. Suppose you wanted to flatten a nested object of data that you aggregated to build your app.

const cat = {
  breed: 'Siamese',
  age: 3,
  colors: {
    body: 'cream',
    eyes: 'blue',
  },
  personality: {
    affectionate: true,
    intelligent: true,
    independent: false,
  },
};

Let's take this nested object for example. How would recursion help you in solving the problem? What would be your base case and recursive case? Let's write our recursive function to flatten the object.

function flatten(obj, prefix = '') {
  const result = {};

  for (const [key, value] of Object.entries(obj)) {
    const pre = prefix.length ? prefix + '.' : '';
    // base case
    if (typeof value === 'object' && value !== null && !Array.isArray(value))     {
      // recursive case
      Object.assign(result, flatten(value, pre + key));
    } else {
      result[pre + key] = value;
    }
  }

  return result;
}

const flattenedCat = flatten(cat);
console.log(flattenedCat);

This example was a bit more complex, but the same principles we used to solve the first problem apply to this problem as well. First, the function works by looping over the object, iterating over each key-value pair. We then establish our base case to check and see if the argument is an object; if not, the function adds the key-value pair to the result object. Finally, we can write our recursive case by using object.assign to merge result with our recursive call flattenObject then returning result thus forming a new flattened object.

{
breed: "Siamese"
age: 3
colors.body: "cream"
colors.eyes: "blue"
personality.affectionate: true
personality.independent: false
personality.intelligent: true
}

Now that you know how recursion works by solving a real-world problem, you can teach your non-programming friends about recursion! 🥳

Overall, recursion is a powerful technique that enables elegant solutions to problems that involve repetitive patterns. With patience and practice, you can unlock the full potential of recursion and take your programming skills to new heights. 🚀