Рекурсия, пример применения рекурсии

Question

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}]
  }
};

// The function to do the job
function sumSalaries(department) {
  if (Array.isArray(department)) { // case (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

Этот код предназначен для использования рекурсии при расчете общей заработной платы в подразделениях компании. Пожалуйста, объясни мне это. В примере учебника, рекурсивные обходы, после запуска первого случая (мы рассчитываем зарплату в отделе продаж), функция возвращает эту зарплату. Так зачем же идти дальше и вычислять другой случай (отдел разработки), если в первом расчете есть оператор возврата? Разве это не должно нарушить поток? И как это сумма дела 1 и общая сумма дела 2?

Answer 1

/*  1 */ function sumSalaries(department) {
/*  2 */ if (Array.isArray(department)) { // case (1)
/*  3 */     return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
/*  4 */   } else { // case (2)
/*  5 */     let sum = 0;
/*  6 */     for (let subdep of Object.values(department)) {
/*  7 */       sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
/*  8 */     }
/*  9 */     return sum;
/* 10 */   }
/* 11 */ }

/*  (1) */ sumSalaries (company) {
/*  (2) */   Array .isArray (company) //=> false, so hit branch 2
/*  (5) */     sum = 0
/*  (6) */     Object .values (company) //=> [<sales>, <development>]
/*  (6) */     [<sales>, <development>] .for Each ... 
/*  (7) */       sumSalaries (<sales>) {
/*  (2) */         Array .isArray (<sales>) //=> true, so hit branch 1           //       John   Alice
/*  (3) */           <sales>.reduce((prev, current) => prev + current.salary, 0) //=> 0 + 1000 + 1600 = 2600
/*  (3) */           return 2600
/* (10) */       }
/*  (7) */       sum = 0 + 2600 = 2600
/*  (7) */       sumSalaries (<development>) {
/*  (2) */         Array.isArray (<development) //=> false, so hit branch 2
/*  (5) */           sum = 0  // (different instance of `sum` from above)
/*  (6) */           Object.values (<development>) //=> [<sites>, <internal>]
/*  (6) */           [<sites>, <internal>] .for Each ...  
/*  (7) */             sumSalaries (<sites>) {
/*  (2) */               Array.isArray (<sites>) //=> true, so hit branch 1            //       Peter  Alex
/*  (3) */                 <sites>.reduce((prev, current) => prev + current.salary, 0) //=> 0 + 2000 + 1800 = 3800
/*  (3) */                 return 3800
/* (10) */             }
/*  (7) */             sum = 0 + 3800
/*  (7) */             sumSalaries (<internals>) {
/*  (2) */               Array.isArray (<internals>) //=> true, so hit branch 1               Jack
/*  (3) */                 <internals>.reduce((prev, current) => prev + current.salary, 0) //=> 0 + 1300 = 1300
/* (10) */                 return 1300
/* (10) */             }
/*  (7) */             sum = 3800 + 1300 = 5100
/*  (9) */           return 5100
/* (10) */       }
/*  (7) */       sum = 2600 + 5100 = 7700  // (back to the original `sum`)
/*  (9) */       return 7700
/* (11) */ }

---

Но в этом коде есть что-то странное. Во-первых, он использует reduce для суммирования значений в одном случае и sum = 0 ... for (...) { sum += ... } ... return sum для другого; это странно Во-вторых, он использует существенно другое имя переменной для внутренней переменной, которую вы собираетесь предоставить в качестве параметра для рекурсивного вызова. Но структура данных не предполагает этого; Компания структурирована так же, как любой отдел или подразделение. Это различие между "department" и "subdep" затрудняет понимание рекурсивного характера проблемы. Обычно, когда мне нужны два разных имени для структуры данных, я пытаюсь сделать их похожими. Я мог бы, например, использовать сокращение dept вместо subdep.

Итак, я бы написал это по-другому. Вот другая версия, использующая вспомогательную функцию, которая суммирует массив чисел. Хотя это выглядит совсем иначе, лежащий в основе лог c полностью такой же:

const sum = (ns) => ns .reduce ((t, n) => t + n, 0)

const sumSalaries = (department) =>
  Array .isArray (department) 
    ? sum (department .map (empl => empl .salary))
    : sum (Object .values (department) .map (sumSalaries))

const 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}]}}

console .log (sumSalaries (company))

Answer 2

Это потому, что строка sum += sumSalaries(subdep) создает несколько вызовов функций, и каждый из них является независимым.

Давайте разбить l oop на отдельные вызовы функций

for (let subdep of Object.values(department)) {
   sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
}

- это всего лишь

sum += sumSalaries(department.sales);
sum += sumSalaries(department.development);

Каждый из приведенных выше вызовов функций будет выполнен самостоятельно и вернется Значение. Итак, когда первый вызов возвращает что-то, он просто завершает свою собственную функцию, а не функцию root.