Python: рекурсия

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

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

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

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

Базовый случай и рекурсивный шаг

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

def factorial(n):
\( if n == 0: \)
return 1
\( return n \times factorial(n - 1) \)

При вызове factorial(3) Python сначала вычисляет 3 × factorial(2), затем 2 × factorial(1), затем 1 × factorial(0). На нулевом шаге функция возвращает 1, после чего отложенные вычисления идут обратно: 1, затем 2, затем 6.

Следи за условием выхода особенно внимательно. Если написать n + 1 вместо n − 1, аргумент будет удаляться от нуля. Если базового случая нет, Python накопит слишком много вызовов и сообщит об ошибке глубины рекурсии.

Как читать рекурсивный код

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

Полезно составлять таблицу: номер вызова, значение аргумента и действие после возвращения. Например, для factorial(4) аргументы идут так: 4 → 3 → 2 → 1 → 0. Только после 0 вычисления начинают сворачиваться в обратном направлении.

Вызов	Что происходит	Результат
factorial(4)	4 × factorial(3)	ожидает 24
factorial(3)	3 × factorial(2)	ожидает 6
factorial(2)	2 × factorial(1)	ожидает 2
factorial(1)	1 × factorial(0)	ожидает 1
factorial(0)	базовый случай	1

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

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

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

Найдём сумму цифр положительного числа. Для числа 572 последняя цифра получается остатком от деления на 10: 572 % 10 равно 2. Остальные цифры — это 572 // 10, то есть 57. Поэтому сумма цифр равна 2 плюс сумма цифр числа 57.

def digit_sum(n):
if n < 10:
return n
\( return n \% 10 + digit_sum(n // 10) \)

digit_sum(572)
\( 2 + digit_sum(57) \)
\( 2 + 7 + digit_sum(5) \)
\( 2 + 7 + 5 \)
14

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

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

Типичные ошибки и рекурсия против цикла

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

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

Перед запуском проверь решение по чек-листу:

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

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

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

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

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

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