Recursion to Iteration Recipe

by Peer Reynders

JavaScript

// from: https://javascript.info/recursion#recursive-traversals
//
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);
  
// 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;
}

console.log(sumSalaries(company)); // 7700

/*
// 1. 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;
}

// 2. 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...