Шпаргалка: рекурсия: примеры

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

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

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

У любой корректной рекурсии есть две обязательные части:

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

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

Как работает вызов функции

Рассмотрим функцию, которая считает сумму чисел от 1 до n. Для n = 4 она не складывает всё сразу, а превращает задачу в цепочку: 4 + сумма от 1 до 3. Затем появляются 3 + сумма от 1 до 2 и 2 + сумма от 1 до 1.

Базовый случай здесь — n = 1. Сумма от 1 до 1 равна 1, поэтому дальше вызывать функцию не нужно. После этого вычисления возвращаются в обратном порядке: сначала находится сумма для 2, потом для 3, затем для 4.

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

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

Для задач со значениями 0 удобно выбрать базовый случай n = 0. Тогда сумма от 1 до 0 считается равной 0, а переход записывается как sum(n) = n + sum(n − 1).

Разобранный пример: факториал

Факториал натурального числа n обозначают n! и определяют так: n! = 1 × 2 × 3 × … × n. В математике отдельно принято считать, что 0! = 1. Это не случайная договорённость: такое значение делает рекурсивную формулу удобной и непрерывной по смыслу.

Рекурсивное правило выглядит так: n! = n × (n − 1)!, а базовый случай — 0! = 1. Разберём вычисление 4! полностью.

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

В программе сначала идут вызовы до fact(0), а затем возвраты: fact(0) возвращает 1, fact(1) возвращает 1 × 1, fact(2) — 2 × 1, fact(3) — 3 × 2, fact(4) — 4 × 6.

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

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

Самая частая ошибка — забыть базовый случай. Не менее опасно написать его неверно: например, останавливать функцию при n = 1, но затем вызывать её с нулём. Всегда проверь самые маленькие допустимые входные данные вручную.

Вторая проблема — отсутствие продвижения к базе. Вызов f(n) внутри f(n) не меняет задачу. Вызов f(n − 1) меняет, но только если n действительно положительно.

Третья ошибка связана с повторными вычислениями. В рекурсивном алгоритме для чисел Фибоначчи выражение fib(n − 1) + fib(n − 2) много раз считает одни и те же значения. В таком случае помогают запоминание результатов или цикл.

Ситуация	Рекурсия удобна	Лучше выбрать цикл
Один простой повтор	Если формула естественно описывает задачу	Если важны память и скорость
Дерево или вложенные папки	Да, структура сама ветвится	Возможен стек, если глубина велика
Большое число шагов	Только с контролем глубины	Чаще безопаснее цикл

Как решать рекурсивные задачи

Начни не с кода, а с определения результата. Спроси: что должна вернуть функция для одного входного значения? Затем найди самый маленький случай. Для суммы это 0, для факториала — 0!, для обхода последовательности — конец последовательности.

После этого сформулируй переход одной фразой: «Ответ для n равен действию над n и ответом для меньшего аргумента». Запиши уменьшение явно: n − 1, n − 2 или переход к следующей вершине.

Проверь цепочку на двух-трёх маленьких значениях. Например, для степеней: aⁿ = a × aⁿ⁻¹, а базовый случай a⁰ = 1. Для быстрого возведения в степень можно использовать деление показателя пополам, но там нужно внимательно обработать чётность.

Если задача ветвится, нарисуй дерево вызовов. Так проще увидеть повторения и понять, нужна ли таблица уже найденных ответов. При подготовке к ОГЭ полезно отдельно тренировать чтение готового рекурсивного кода, а не только написание своего. В разделе подготовки к ОГЭ можно закреплять такие алгоритмы на практике.

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

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

Для факториала: n! = n × (n − 1)!, 0! = 1. Для суммы: sum(n) = n + sum(n − 1), sum(0) = 0. Результат рекурсивной функции часто формируется при возврате из вызовов, поэтому полезно прослеживать цепочку в обе стороны.

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

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