Не понимаю рекурсию

Что такое рекурсия и зачем она нужна

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

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

1. Базовый случай — условие остановки.
2. Рекурсивный шаг — вызов той же функции для уменьшенной задачи.

Например, чтобы посчитать сумму чисел от 1 до n, можно взять последнее число n и прибавить сумму чисел от 1 до n − 1. Так большая задача превращается в почти такую же, но меньшего размера.

\( S(n) = n + S(n - 1) \)
\( S(1) = 1 \)

Запись S(1) = 1 — это базовый случай. Без него программа не поймёт, когда остановиться.

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

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

Рассмотрим факториал. Факториал числа n обозначают n! и находят так: n! = n × (n − 1) × … × 1. Рекурсивное определение выглядит проще:

\( fact(n) = n \times fact(n - 1) \)
\( fact(1) = 1 \)

Для fact(4) компьютер сначала запомнит fact(4), затем fact(3), fact(2), fact(1). На fact(1) сработает остановка. После этого вычисления пойдут обратно: 1 × 2, затем 2 × 3, затем 6 × 4. Ответ — 24.

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

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

Решим задачу: найти сумму чисел от 1 до 4 с помощью рекурсии. Обозначим функцию sum(n). Если n равно 1, она возвращает 1. Иначе возвращает n плюс результат для n − 1.

\( sum(4) \to 4 + sum(3) \)
\( sum(3) \to 3 + sum(2) \)
\( sum(2) \to 2 + sum(1) \)
sum(1) → 1
\( sum(2) \to 2 + 1 = 3 \)
\( sum(3) \to 3 + 3 = 6 \)
\( sum(4) \to 4 + 6 = 10 \)

Разберём этот пример полностью. Сначала функция получает 4 и ещё не может вернуть окончательный результат: ей нужно узнать sum(3). Вызов с 3 ждёт sum(2), а вызов с 2 ждёт sum(1). Когда приходит значение 1, ожидание заканчивается. Каждый предыдущий вызов получает ответ и выполняет своё сложение.

В программе это можно представить так: если n ≥ 1, вернуть n + sum(n − 1); иначе вернуть 0. Вариант с нулём удобен, если функция должна работать и для n = 0. Главное — заранее определить допустимые входные данные.

Для n = 4 результат 10. При больших n рекурсивный вариант может занимать память из-за цепочки вызовов, поэтому иногда обычный цикл практичнее.

Где рекурсия встречается на практике

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

Задача	Что уменьшается	Базовый случай
Сумма чисел	n	n = 1 или n = 0
Факториал	n	n = 1
Обход папок	число вложенных уровней	файл или пустая папка
Бинарный поиск	размер диапазона	элемент найден или диапазон пуст

В задачах на перебор рекурсия помогает попробовать один вариант, перейти к следующему шагу, а затем вернуться и попробовать другой. Такой возврат называют backtracking, или поиском с возвратом. Например, так решают задачи о расстановке ферзей и составлении слов из букв.

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

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

Типичные ошибки и проверка решения

Первая ошибка — забыть базовый случай. Тогда функция вызывает себя бесконечно, пока программа не остановится из-за переполнения стека. Вторая — написать базовый случай, но не приблизить к нему аргумент. Например, вызов f(n) внутри f(n) не меняет задачу, а значит, остановка недостижима.

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

Перед проверкой прогони три маленьких случая: минимальный допустимый вход, обычный пример и значение, на котором граница меняется. Для суммы проверь 1, 4 и 0, если он разрешён условием. Отдельно оцени глубину рекурсии: иногда алгоритм правильный логически, но слишком глубокий для памяти.

Если готовишься к экзамену, полезно разобрать задачи на рекуррентные формулы и перебор в разделе для подготовки к ОГЭ или материалах для ЕГЭ.

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

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

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

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. Начни с коротких цепочек вызовов, затем переходи к факториалу, суммам и перебору. Так ты проверишь не только определение, но и реальное понимание.