Содержание

Рекурсия в программировании: когда и зачем её применять

Рекурсия – это прием программирования, при котором программа вызывает саму себя либо непосредственно, либо косвенно. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной.

Как правило, неопытный программист, узнав про рекурсию, испытывает легкое недоумение. Первая мысль – это бессмысленно!!! Такой ряд вызовов превратиться в вечный цикл, похожий на змею, которая съела сама себя, или приведет к ошибке на этапе выполнения, когда программа поглотит все ресурсы памяти. Однако рекурсия – это превосходный инструмент, который при умелом и правильном использовании поможет программисту решить множество сложных задач.

Определение рекурсивной функции

Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции. 

// пример для C++
int a()
{.....a().....}

Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.

Например: 

// пример для C++
a(){.....b().....}
b(){.....c().....}
c(){.....a().....}

Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.

Рекурсии или итерации?

С точки зрения теории, любой алгоритм, который можно реализовать рекурсивно, совершенно спокойно реализуется итеративно.

Рекурсия производит вычисления гораздо медленнее, чем итерация. Кроме того, рекурсия потребляет намного больше оперативной памяти в момент своей работы.

Значит ли это, что рекурсия бесполезна? Ни в коем случае!!! Существует ряд задач, для которых рекурсивное решение тонко и красиво, а итеративное – сложно, громоздко и неестественно.

Когда применять рекурсию?

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

Пример JS: Рекурсивный подсчёт зарплат во вложенном объекте

Допустим, у нас есть объект company, представляющий структуру компании. Внутри могут быть как массивы сотрудников, так и вложенные департаменты. Наша задача — рекурсивно посчитать сумму всех зарплат. 

// Объект может содержать неизвестное количество департаментов и сотрудников
let company = {
  sales: [
    { name: 'John', salary: 1000 },
    { name: 'Alice', salary: 600 }
  ],
  development: { 
    web: [
      { name: 'Peter', salary: 2000 },
      { name: 'Alex', salary: 1800 }
    ],
    internals: [
      { name: 'Jack', salary: 1300 }
    ]
  }
};

🧠 Алгоритм:

Переменная sum создаётся заново на каждом этапе рекурсии, поэтому она не мешает другим вызовам и не "сбрасывает" общий результат. Подробнее о методе reduce: 📚 MDN – Array.prototype.reduce()

✅ Решение с использованием рекурсии и reduce: 

function sumSalaries(department) {
  // Проверяем: если department — массив (список сотрудников)
  if (Array.isArray(department)) {
    // Суммируем все зарплаты сотрудников
    return department.reduce((sum, employee) => sum + employee.salary, 0);
  } else {
    // Если это объект (например, департамент с подразделениями)
    let sum = 0;
 
    // Проходим по всем значениям объекта (поддепартаментам)
    for (let subDep of Object.values(department)) {
      // Рекурсивно вызываем ту же функцию
      sum += sumSalaries(subDep);
    }
 
    return sum;
  }
}
 
console.log(`Сумма зарплат сотрудников = ${sumSalaries(company)}`);
Сумма зарплат сотрудников = 6700

Читайте также