Discussion on: Recursion in JavaScript

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]