Рекурсия в Python: от факториала до задач ЕГЭ

Рекурсия — приём, при котором функция вызывает саму себя, но с задачей чуть меньше исходной. Со стороны похоже на фокус, но держится всё на двух опорах. Базовый случай — условие, при котором функция возвращает ответ сразу, ничего не вызывая: дно, ниже которого спускаться не нужно. Рекурсивный шаг — сведение текущей задачи к такой же, но меньшего размера. Пока шаг приближает аргумент к базе, рано или поздно дно достигается, и ответы начинают возвращаться вверх по цепочке вызовов. В 11 классе рекурсия выходит на первый план не ради красоты: задание 16 ЕГЭ прямо проверяет, умеешь ли ты читать рекурсивную функцию и предсказывать, что она выведет. Разберём факториал, взрыв вызовов на Фибоначчи и соберём технику ручной трассировки.

Факториал: база и шаг

Вход в тему — факториал: def f(n): return 1 if n <= 1 else n * f(n - 1) Читается так: если n <= 1 — база, возвращаем 1; иначе шаг — n умножить на f(n - 1), ту же функцию с числом на единицу меньше. Аргумент при каждом вызове приближается к базе, поэтому бесконечного спуска не будет. А вот сломать это равновесие легко: смени базу на n <= 0 при том же шаге — и вызов f(0) уйдёт в минус единицу, минус два и никогда не остановится. Формула есть, база вроде есть, но до неё не добраться. Два контрольных вопроса к любой рекурсии: есть ли база и приближает ли шаг аргумент к ней.

Трассируем f(4). Вызовы погружаются вниз: f(4) замирает на вычислении 4 f(3), f(3) — на 3 f(2), f(2) — на 2 * f(1). Каждый недовершённый вызов Python держит в стеке вызовов — стопке кадров, где работа идёт только с верхним. В самый глубокий момент в стопке четыре кадра: f(4), f(3), f(2), f(1). Дальше раскрутка: f(1) возвращает 1, f(2) досчитывает 2 1 = 2, f(3) — 3 2 = 6, f(4) — 4 * 6 = 24. Ответ 24, а глубина рекурсии — сколько кадров сидело в стеке одновременно — равна четырём.

• Где базовый случай и срабатывает ли он гарантированно?
• Приближает ли рекурсивный шаг аргумент к базе?
• Что возвращается в каждой ветке — не потерян ли где-то return?

Фибоначчи: когда рекурсия взрывается

Числа Фибоначчи — две базы и два вызова: def fib(n): if n <= 2: return 1 return fib(n - 1) + fib(n - 2) Формула честная, но посмотри на работу: fib(5) требует fib(4) и fib(3), fib(4) — fib(3) и fib(2), и каждое поддерево тянет всё заново. Дерево вызовов ветвится, и одна и та же работа повторяется: при вычислении fib(5) значение fib(2) считается трижды, fib(3) — дважды. Число вызовов C(n) само живёт по рекурсии C(n) = C(n - 1) + C(n - 2) + 1 и растёт примерно как сами числа Фибоначчи, то есть экспоненциально. Уже fib(30) — больше миллиона вызовов ради ответа 832040.

Замер подтверждает скорость роста. В таблице — значение fib(n) и число вызовов наивной рекурсии при базе fib(1) = fib(2) = 1:

Лечение называется мемоизация: готовые ответы складываются в кэш, и повторный вызов с тем же аргументом забирает результат вместо нового спуска. В Python хватает одной строки — декоратора из functools: from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 2: return 1 return fib(n - 1) + fib(n - 2) Формула не изменилась ни на знак — изменилось то, что каждый fib(k) вычисляется один раз, а повторные вызовы бьют в кэш. fib(20) вместо 13529 вызовов делает порядка двадцати вычислений, а fib(100) с кэшем отвечает мгновенно. Правило: чистая функция с повторяющимися аргументами — вешай lru_cache.

Рекурсия против цикла

Рекурсия — инструмент, а не самоцель: для плоских данных цикл честнее. Сумма элементов массива через рекурсию работает, но каждый элемент — лишний кадр стека, лишние расходы и риск упереться в лимит глубины: total = 0 for x in [5, 3, 8]: total += x Цикл делает то же без накладных расходов. Всё плоское — суммирование, средний балл, максимум, вывод чисел от 1 до 100 — спокойно живёт в цикле и без сюрпризов.

Циклу тесно там, где структура вложенная. Обход папок: внутри папки лежат папки, внутри них ещё — глубина заранее неизвестна, цикл с фиксированным числом уровней бессилен, а рекурсия разворачивается ровно на нужную глубину. Вторая классика — Ханойские башни: перенести пирамиду из n дисков — это перенести n - 1 диск на запасной стержень, переместить самый большой и снова перенести n - 1: def hanoi(n, src, tmp, dst): if n == 0: return hanoi(n - 1, src, dst, tmp) print("диск", n, ":", src, "->", dst) hanoi(n - 1, tmp, src, dst) Сделать это циклом — значит вручную управлять стеком, то есть писать ту же рекурсию руками. Правило выбора: вложенные структуры и самоподобные задачи — рекурсия, ровные списки — цикл.

Задание 16: функция с двумя ветками

В задании 16 ЕГЭ рекурсия обычно с двумя ветками: F(1) = 1; F(2) = 2; при n > 2 верно F(n) = 2 F(n - 1) + F(n - 2). Вопрос — «что выведет print(F(5))». Метод один: считать от базы вверх, ведя таблицу значений. F(3) = 2 F(2) + F(1) = 2 2 + 1 = 5. F(4) = 2 F(3) + F(2) = 2 5 + 2 = 12. F(5) = 2 F(4) + F(3) = 2 * 12 + 5 = 29. Ответ 29 — без догадок и без запуска кода. Если спрашивают число вызовов, веди вторую колонку: каждый вызов — единица плюс вызовы обеих веток. Частые промахи: перепутать ветки местами, потерять множитель перед F(n - 1) или считать сверху вниз, когда нижние уровни ещё пусты.

Второй сюжет — рекурсия с одной веткой. Сумма цифр: def sd(n): if n < 10: return n return n % 10 + sd(n // 10) Вызов sd(47): число двузначное, значит 7 + sd(4); sd(4) — база, ответ 4; итог 11. Шаг отрезает последнюю цифру через n % 10, а остаток n // 10 уходит в рекурсию и неумолимо уменьшается до однозначного числа. Это готовый шаблон цифровых задач: количество цифр, сумма чётных цифр, число нечётных — меняется только пара «шаг и база».

Третий шаблон — алгоритм Евклида, НОД двух чисел: def gcd(a, b): if b == 0: return a return gcd(b, a % b) Уменьшается второй аргумент: остаток a % b всегда меньше b, поэтому база b == 0 достижима гарантированно. Вызов gcd(48, 18): 48 % 18 = 12 — дальше gcd(18, 12), затем gcd(12, 6) и gcd(6, 0); база возвращает 6. НОД(48, 18) = 6, и разложение на множители это подтверждает. Заметь: рекурсивный вызов стоит последним действием, но кадры стека Python всё равно копит — «хвостовая» форма здесь ничего не экономит.

Ловушки

План отработки простой. Первый шаг — факториал и сумма цифр по памяти за минуту: два шаблона закрывают половину вопросов. Второй — Фибоначчи в двух версиях, с lru_cache и без, плюс ручной подсчёт вызовов fib(5) со сверкой по таблице урока. Третий — задания 16 прошлых лет по технике «от базы вверх»: одна таблица значений отвечает и на вопрос «что выведет», и на вопрос «сколько вызовов». Финальный рубеж — Ханойские башни: сможешь объяснить, почему для n дисков нужно 2^n - 1 перемещение, — рекурсия твоя.

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема