Рекурсия — это когда метод вызывает сам себя. На первый взгляд это похоже на ошибку (не зациклится ли программа навсегда?), но это один из самых элегантных приёмов программирования. Некоторые задачи решаются рекурсией так естественно, что любое другое решение выглядит громоздким. Разберём, как это работает и когда уместно. Под капотом рекурсия опирается на стек вызовов, о котором мы уже говорили.

Идея: свести задачу к более простой

Возьмём факториал: 5! = 5 × 4 × 3 × 2 × 1 = 120. Ключевое наблюдение — факториал определяется через самого себя: 5! = 5 × 4!, а 4! = 4 × 3!, и так далее. То есть задачу «посчитать n!» можно свести к более простой задаче «посчитать (n−1)!» и умножить результат на n.

int factorial(int n) {
    if (n <= 1) return 1;          // базовое условие
    return n * factorial(n - 1);   // шаг к более простой задаче
}

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

Базовое условие — что останавливает рекурсию

Если бы метод вызывал себя без остановки, он делал бы это бесконечно, пока программа не рухнет. Поэтому у любого рекурсивного метода обязательно есть базовое условие — случай, настолько простой, что ответ известен сразу, без нового вызова. У факториала это n ≤ 1 → 1. Каждый рекурсивный вызов подбирается к базовому условию (аргумент уменьшается), и рано или поздно упирается в него — тогда цепочка вызовов начинает разворачиваться обратно.

Хорошая аналогия — эстафета. Вам поручили посчитать 5!. Вы знаете, что это 5 × 4!, но 4! считать не умеете, поэтому передаёте задачу дальше: «посчитай мне 4!». Тот передаёт «посчитай 3!» и так до того, кто может ответить сразу («1! = 1»). С этого момента ответы бегут обратно по цепочке, каждый домножается — и до вас доходит 120.

Что происходит в стеке вызовов

Пока цепочка вызовов «идёт вглубь», все незавершённые вызовы должны где-то храниться — со своими аргументами и точкой, куда вернуть управление. Для этого язык использует стек вызовов: при каждом вызове туда кладётся кадр (аргументы + адрес возврата), при возврате — снимается. Именно поэтому для factorial(5) в какой-то момент в стеке одновременно живут пять вложенных вызовов, а самый глубокий (n = 1) первым отдаёт результат.

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

Три признака рекурсивного метода

Обобщим. Метод рекурсивен, если:

  1. вызывает сам себя;
  2. этот вызов решает более простую версию той же задачи (меньший аргумент, меньший диапазон);
  3. существует базовый случай, достаточно простой, чтобы решить его без рекурсии.

Нет пункта 3 — рекурсия бесконечна. Нет пункта 2 — задача не «сходится» к базовому случаю.

Рекурсия и математическая индукция

Рекурсия — программный близнец математической индукции: способа определить или доказать что-то «через себя». Факториал индуктивно задаётся двумя строчками: f(1) = 1 и f(n) = n · f(n−1). Кажется, что определять понятие через само себя — порочный круг, но при наличии базового случая это совершенно законно: база даёт точку опоры, а шаг сводит сложное к простому.

Где рекурсия особенно к месту

Рекурсия сияет там, где задача естественно разбивается на подзадачи того же вида.

Ханойская башня. Головоломка: перенести пирамидку из дисков с одного стержня на другой, не кладя больший диск на меньший. Рекурсивное решение до смешного короткое: чтобы перенести n дисков, перенеси n−1 верхних на промежуточный стержень, переложи самый большой на целевой, а потом перенеси те же n−1 поверх него. Каждый шаг — та же задача меньшего размера. Циклом это решается куда болезненнее.

Сортировка слиянием (merge sort). Одна из первых по-настоящему быстрых сортировок и яркий пример подхода «разделяй и властвуй»: массив делят пополам, каждую половину рекурсивно сортируют, а затем сливают два упорядоченных куска в один за линейный проход. Деление даёт log N уровней, слияние на каждом уровне — N работы, итого O(N·log N) — принципиально быстрее, чем O(N²) у простых сортировок. Плата — дополнительная память под слияние. Тот же принцип «дели пополам» лежит и в основе рекурсивного двоичного поиска.

Рекурсия ещё пригодится нам при обходе деревьев и графов — там она особенно естественна.

Коротко

  • Рекурсия — метод вызывает сам себя, сводя задачу к более простой версии той же задачи.
  • Обязателен базовый случай — простой вариант с готовым ответом; он останавливает рекурсию, после чего результаты разворачиваются обратно по цепочке.
  • Незавершённые вызовы хранятся в стеке вызовов; отсюда накладные расходы по времени и памяти и риск переполнения стека.
  • Рекурсию применяют ради ясности, а не скорости: её обычно можно переписать циклом, который быстрее, но менее нагляден.
  • Она незаменима в задачах «разделяй и властвуй» — сортировка слиянием O(N·log N), Ханойская башня, обход деревьев и графов.

Дальше — нетривиальная сортировка: быстрые алгоритмы (Шелл, быстрая сортировка), которые обгоняют простые методы и активно используют идеи из этой статьи.