Рекурсия в алгоритмах

Что такое рекурсия

Если задача кажется слишком большой и запутанной, рекурсия помогает разложить её на одинаковые маленькие шаги. Ты учишься замечать повторяющуюся структуру, правильно задавать условие остановки и уверенно решать задачи по алгоритмам на уроках и экзамене.

Рекурсивным называют алгоритм, который вызывает сам себя с другими, обычно меньшими, данными. Такой подход особенно удобен, когда объект состоит из похожих частей: число раскладывается на разряды, папка содержит вложенные папки, а дерево состоит из ветвей.

У любой корректной рекурсии есть две обязательные части. Базовый случай сообщает, когда ответ уже известен и дальнейшие вызовы не нужны. Рекурсивный шаг уменьшает задачу и снова запускает алгоритм. Если забыть хотя бы одну часть, программа может зациклиться или вернуть неверный результат.

Например, факториал числа n можно определить так: n! = n × (n − 1)!, а 0! = 1. Здесь равенство для нуля является базовым случаем, а умножение на предыдущее число — рекурсивным шагом.

Как работает рекурсивный вызов

Представь функцию как инструкцию с памятью. При каждом вызове компьютер сохраняет текущие значения, чтобы после завершения внутреннего вызова продолжить работу. Эти сохранённые состояния образуют стек вызовов: последний начатый вызов завершится первым.

Рассмотрим вычисление факториала 4. Сначала функция получает 4 и обращается к факториалу 3. Затем появляются вызовы для 2, 1 и 0. На нуле функция возвращает 1, после чего ответы начинают возвращаться в обратном направлении.

fact(4) → 4 × fact(3)
→ 4 × 3 × fact(2)
→ 4 × 3 × 2 × fact(1)
→ 4 × 3 × 2 × 1 × fact(0)
\( \to 4 \times 3 \times 2 \times 1 \times 1 = 24 \)

Важно отличать движение «вглубь» от обратного хода. Сначала накапливаются незавершённые умножения, а после базового случая они выполняются. Чем больше глубина, тем больше памяти занимает стек. Поэтому рекурсия выразительна, но не всегда экономна.

Разобранный пример: сумма цифр

Найдём сумму цифр натурального числа. У числа 583 последняя цифра равна 3, а оставшаяся часть — 58. Значит, можно прибавить последнюю цифру к сумме цифр числа 58. Операция остатка от деления на 10 даёт последнюю цифру, а целочисленное деление на 10 убирает её.

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

\( sum(583) = 3 + sum(58) \)
\( sum(58) = 8 + sum(5) \)
\( sum(5) = 5 \)
\( sum(58) = 8 + 5 = 13 \)
\( sum(583) = 3 + 13 = 16 \)

Алгоритм завершится, потому что после каждого шага число уменьшается: 583 → 58 → 5. В коде условие может выглядеть как «если n < 10, вернуть n», а общий случай — «вернуть n mod 10 + sum(n div 10)». Здесь div означает целочисленное деление.

Похожий принцип используется для подсчёта цифр, разворота числа и проверки, является ли строка палиндромом. В каждом случае сначала найди часть, которую можно убрать, не потеряв структуру задачи.

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

Рекурсия и итерация

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

Признак	Рекурсия	Цикл
Описание	Функция вызывает себя	Повторение команд в цикле
Память	Расходуется стек вызовов	Чаще требуется постоянная память
Удобна для	Деревьев, вложенных объектов	Линейного подсчёта и прохода

Например, факториал можно вычислять последовательным умножением от 1 до n. Результат будет тем же, но не появится цепочка fact(n) → fact(n − 1) → … . В задачах экзамена сначала оцени форму условия: если каждый шаг просто повторяет действие, цикл может быть практичнее.

В задачах с деревьями рекурсия часто естественнее: обработать вершину, затем отдельно обработать левую и правую ветви. При этом нужно контролировать глубину и не выполнять одинаковые вычисления без необходимости.

Типичные ошибки

Первая ошибка — отсутствие базового случая. Функция продолжает вызывать себя даже для нуля или пустой строки. Вторая — задача не уменьшается: например, вызов сделан с тем же n, поэтому завершения не будет.

Третья ошибка связана с неправильным порядком действий. Если нужно сначала обработать данные, а потом выполнить рекурсивный вызов, получится один алгоритм; если поменять порядок, получится другой. При подсчёте элементов дерева важно отдельно понять, когда учитывается текущая вершина.

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

Проверяй решение на минимальных данных: 0, 1, пустом списке или одном элементе. Затем возьми пример из двух-трёх элементов и только после этого рассматривай большие входные данные.

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

Что запомнить

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

Перед решением спроси себя: «Какая самая маленькая версия задачи? Что я уберу на одном шаге? Как соединю полученный ответ с текущими данными?» Для суммы цифр убирается последняя цифра, для дерева рассматриваются дочерние вершины, для строки можно сравнивать крайние символы.

Не всякую задачу нужно решать рекурсивно: сравни глубину, расход памяти и ясность записи с вариантом через цикл. Зарегистрируйся и реши 5 заданий бесплатно в личном кабинете, чтобы закрепить базовый случай и рекурсивный шаг на практике.