DEV Community

Kade Esterline
Kade Esterline

Posted on

Recursion in JavaScript

You've probably heard of recursion and know that it involves writing a function that calls itself again. At first this can be kind of hard to wrap your head around, but I'm going to try to break it down as best as I can.

recursion meme

The Call Stack

First let's talk about how the call stack actually works in JavaScript. The call stack is a stack data structure, just like it sounds. I like to think of the call stack as a stack of papers. Imagine every time a function is called a piece of paper is added to the stack. JavaScript can only work from the top of the stack down, so as more and more functions get called inside of other functions that stack grows in size. If you had a function called main that called a second function inside of itself called nested, the call stack would first have main put in the stack, then when nested is called it's put on top of main. Once nested is finished being evaluated and returns it's value to main, main can finish being evaluated and also pushed off the stack. Here's what that would look like:

nested function call example

Recursive vs Iterative

Now let's circle back to recursion. We know that every time we call a function it's put on top of the call stack until it's evaluated and then popped off the top of the call stack. With recursion, you just keep calling the same function and keep pushing it onto the call stack. Obviously you can't just keep calling the same function over and over with no limit, you'll overflow the stack.

To make sure our recursive functions stop being called it's actually pretty similar to a loop. You make a condition that would stop the function from being called at a certain point(this is just like using i < arr.length; in a for loop). You also have to make sure that every time you call the function recursively that it's getting a different value(this would be kind of like i++ but not really, you'll see in a moment). So if recursion is similar to a loop why not just iterate? Recursion while confusing at first is very concise and often requires less lines of code to do the same task. Here's an example of the same problem done both iteratively and recursively. Both functions will find the factorial of a given number.

Iterative solution

You're probably familiar with a solution like this, there isn't really anything wrong with this solution. It'll work just fine.

recursive solution

As you can see the recursive solution might be a little hard to understand at first. For one, it's a lot less code which is great because it means you can write less code for the same result. At the same time though, it can be hard to see how calling the function within itself is actually working. When returning num * recursiveFactorial(num -1) the original function waits for this new call to resolve. This continues until the base case is met. So, calling recursiveFactorial(3) is the same as calling 3 * 2 * 1.

Resources

For more information on recursion and the call stack you can checkout these links:

I'll do my best to answer any questions in the comments below and feel free to check out some of my other blog posts as well. Thanks for reading!

Discussion (8)

Collapse
sarahalcodes profile image
Sarah Al-Said

Very concise and resourceful, great job Kade!

Collapse
kadeesterline profile image
Kade Esterline Author

Thank you!

Collapse
adam_cyclones profile image
Adam Crockett

Very concise and resourceful, great job Kade!

Collapse
jsanta profile image
Jose Ignacio Santa Cruz G.

Worried about blowing the stack? Trampoline your function. Will make it a little slower but it's memory safe for JavaScript.

Collapse
hareshkotkar5557 profile image
Haresh Kotkar • Edited on

Organized content and well explained
Thanks

Collapse
kadeesterline profile image
Kade Esterline Author

Of course, and thank you!

Collapse
peerreynders profile image
peerreynders

But why bother with recursion in JavaScript, especially when you can blow the stack?

Because it allows you to arrive at simple recursive solutions quickly which can then be transformed to clean iteration with a recipe.

Example: JSFiddle

  1. Start with a body recursive solution

    let company = {
      sales: [
        {
          name: 'John',
          salary: 1000,
        },
        {
          name: 'Alice',
          salary: 1600,
        },
      ],
    
      development: {
        sites: [
          {
            name: 'Peter',
            salary: 2000,
          },
          {
            name: 'Alex',
            salary: 1800,
          },
        ],
    
        internals: [
          {
            name: 'Jack',
            salary: 1300,
          },
        ],
      },
    };
    
    const addEmployeeSalary = (sum, employee) => sum + employee.salary;
    const sumEmployeeSalaries = (employees, total) =>
      employees.reduce(addEmployeeSalary, total);
    
    // Body recursive solution
    function sumSalaries(department, total = 0) {
      // base case - works on leaf nodes; a list of employees
      if (Array.isArray(department)) return sumEmployeeSalaries(department, total);
    
      // recursive case - edge nodes lead to sub departments
      for (let subdep of Object.values(department)) {
        total = sumSalaries(subdep, total); // recursively call for subdepartments, sum the results
      }
      return total;
    }
    
    console.log(sumSalaries(company)); // 7700
    
  2. Convert to a tail recursive solution

    // prime recursion
    const sumSalaries = (department) => sum([department], 0, 0);
    
    function sum(todo, i, total) {
      // base case - nothing left to do
      if (i >= todo.length) return total;
    
      // recursive case
      const current = todo[i];
      if (Array.isArray(current)) {
        // works on a leaf node; a list of employees
        total = sumEmployeeSalaries(current, total);
      } else {
        // edge node leads to sub departments
        todo.push(...Object.values(current));
      }
      return sum(todo, i + 1, total);
    }
    
  3. Introduce a one-shot loop around the function body

    function sum(todo, i, total) {
      while (true) {
        // base case - nothing left to do
        if (i >= todo.length) return total;
    
        // recursive case
        const current = todo[i];
        if (Array.isArray(current)) {
          // works on a leaf node; a list of employees
          total = sumEmployeeSalaries(current, total);
        } else {
          // edge node leads to sub departments
          todo.push(...Object.values(current));
        }
        return sum(todo, i + 1, total);
    
        break;
      }
    }
    
  4. Replace all recursive tail calls f(x=x1, y=y1, ...) with [x, y, ...] = [x1, y1, ...]; continue;

    function sum(todo, i, total) {
      while (true) {
        // base case - nothing left to do
        if (i >= todo.length) return total;
    
        // recursive case
        const current = todo[i];
        if (Array.isArray(current)) {
          // works on a leaf node; a list of employees
          total = sumEmployeeSalaries(current, total);
        } else {
          // edge node leads to sub departments
          todo.push(...Object.values(current));
        }
    
        i += 1;
        continue;
    
        break;
      }
    }
    
  5. Tidy up

    function sum(todo, i, total) {
      while (i < todo.length) {
        const current = todo[i];
        if (Array.isArray(current)) {
          // works on a leaf node; a list of employees
          total = sumEmployeeSalaries(current, total);
        } else {
          // edge node leads to sub departments
          todo.push(...Object.values(current));
        }
    
        i += 1;
      }
      return total;
    }
    
  6. Make more idiomatic

    function sumSalaries(department) {
      let total = 0;
      for (let todo = [department], i = 0; i < todo.length; i += 1) {
        const current = todo[i];
        if (!Array.isArray(current)) {
          // edge node leads to sub departments
          todo.push(...Object.values(current));
          continue;
        }
    
        // works on a leaf node; a list of employees
        total = sumEmployeeSalaries(current, total);
      }
      return total;
    }
    

[ref]

Collapse
kadeesterline profile image
Kade Esterline Author

Thank you for this, seeing a more in depth example in a more practical context helps a lot!