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

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

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

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

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

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

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

Например:

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

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

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

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

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

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

• Обход структур данных, таких как деревья или графы — например, при поиске в глубину (Depth-First Search), где каждый узел вызывает обработку своих потомков.
• Работа с древовидными объектами — рекурсивные функции упрощают обход и форматирование вложенных структур.
• Построение пользовательских интерфейсов — в некоторых фреймворках элементы интерфейса могут формироваться рекурсивно, особенно если они вложены друг в друга.
• Решение задач, сводящихся к подзадачам меньшей размерности — например, вычисление факториала, чисел Фибоначчи, сортировка (QuickSort, MergeSort), разбиение задач на части.

Допустим, у нас есть объект 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

• Задачи Олимпиады для языка C
• Типовые задачи и решения языка CPP
• Динамические структуры данных
• Бинарное дерево С++
• JavaScript: основы, возможности и применение
• ReactJS: Что это такое и с чего начать изучение библиотеки