DEV Community

Discussion on: Recursion in JavaScript

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!