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

> Рекурсия в Python с базой и шагом: факториал, взрыв вызовов на Фибоначчи и спасение через lru_cache, глубина стека и техника «от базы вверх» для задания 16 ЕГЭ.

**Информатика, 11 класс.** Урок бесплатного онлайн-самоучителя «ШкольныйГид». Обновлено: 2026-10-01.

Страница урока: https://shkolniygid.ru/informatika/11-klass/rekursiya-python-11/

Рекурсия — приём, при котором функция вызывает саму себя, но с задачей чуть меньше исходной. Со стороны похоже на фокус, но держится всё на двух опорах. **Базовый случай** — условие, при котором функция возвращает ответ сразу, ничего не вызывая: дно, ниже которого спускаться не нужно. **Рекурсивный шаг** — сведение текущей задачи к такой же, но меньшего размера. Пока шаг приближает аргумент к базе, рано или поздно дно достигается, и ответы начинают возвращаться вверх по цепочке вызовов. В 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, а **глубина рекурсии** — сколько кадров сидело в стеке одновременно — равна четырём.


**Трассировка f(4) по уровням стека**

1. Уровень 1: f(4). База не сработала, вычисление 4 * f(3) замерло в ожидании. В стеке 1 кадр.
2. Уровень 2: f(3). Опять шаг, замерло 3 * f(2). В стеке 2 кадра.
3. Уровень 3: f(2). Замерло 2 * f(1). В стеке 3 кадра.
4. Уровень 4: f(1). Сработала база — возвращаем 1. Глубина 4, ниже спуска нет.
5. Раскрутка вверх: f(2) возвращает 2 * 1 = 2, f(3) — 3 * 2 = 6, f(4) — 4 * 6 = 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:


| n | fib(n) | вызовов без кэша |
| --- | --- | --- |
| 5 | 8 | 15 |
| 10 | 55 | 109 |
| 15 | 610 | 1219 |
| 20 | 6765 | 13529 |

*Число вызовов при вычислении fib(n): C(n) = C(n - 1) + C(n - 2) + 1, что даёт 2 * fib(n) - 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.


> **Ошибки и глубина.** Если базы нет или шаг не приближает к ней аргумент, вызовы не закончатся — но Python остановится сам: при превышении лимита глубины стека программа падает с **RecursionError**. Лимит по умолчанию — около тысячи вложенных вызовов; посмотреть его можно через sys.getrecursionlimit(), а поднять — через sys.setrecursionlimit(3000). Иногда это честно нужно, но поднятие лимита — не лечение: сломанная база всё равно уронит программу, просто позже.


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


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

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 всё равно копит — «хвостовая» форма здесь ничего не экономит.


*[Интерактив: Трассировка gcd(48, 18) — доступен на странице урока]*


### Ловушки


> **Три ловушки.** Первая — потерянный return во вложенном вызове: в одной ветке написано return f(n - 1) + 1, а в другой просто f(n) без return — ветка отдаёт None, и арифметика падает с TypeError. Каждый рекурсивный вызов должен стоять внутри return. Вторая — глобальный счётчик вызовов: без слова global присваивание внутри функции создаёт локальную копию, и внешний счётчик остаётся нулём. Третья — надежда на оптимизацию: «хвостовая» рекурсия, где вызов себя — последнее действие, в некоторых языках превращается в цикл, но Python этого не делает, и стек растёт так же, вплоть до RecursionError.


> **Скоростная трассировка.** Не выписывай вызовы сверху вниз в столбик — рисуй дерево вызовов снизу вверх. Сначала заполни базу: F(1) = 1, F(2) = 2. Потом поднимайся на уровень выше: каждое значение собирается из уже готовых нижних. Такой порядок гарантирует, что к моменту вычисления F(n) оба слагаемых известны, и закрывает самый частый промах задания 16 — попытку считать сверху вниз, когда половина веток пуста.


*[Интерактив: Верно или нет? — доступен на странице урока]*


*[Интерактив: Карточки: быстрые факты — доступен на странице урока]*


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


## Частые вопросы

### Почему рекурсивная функция без базового случая падает с ошибкой?

Вызовы не останавливаются, кадры копятся в стеке, и при превышении лимита глубины Python прерывает программу с RecursionError. Лимит по умолчанию — около тысячи вызовов; его можно поднять через sys.setrecursionlimit, но правильнее починить базу.


### Что делает functools.lru_cache?

Декоратор кэширует результаты вызовов: при повторном обращении с теми же аргументами возвращается готовое значение. Наивный рекурсивный fib с ним превращается из экспоненциального числа вызовов в линейное — каждый fib(k) вычисляется один раз.


### Когда стоит выбрать цикл вместо рекурсии?

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


### Как быстро решить задание 16 ЕГЭ про функцию F(n)?

Считай от базы вверх и держи таблицу значений: сначала F(1) и F(2), затем каждый следующий уровень собирай из уже готовых. Для вопросов о числе вызовов заведи вторую колонку: вызов равен единице плюс вызовы обеих веток.


## Проверь себя (вопросы и ответы)

#### Вопрос 1: Функция задана правилом: F(1) = 1; F(2) = 2; при n > 2 верно F(n) = 2 * F(n - 1) + F(n - 2). Что выведет print(F(5))?
- ✅ 29
- ☐ 24
- ☐ 19
- ☐ 41

*Пояснение: Иди от базы вверх: F(3) = 2 * 2 + 1 = 5, F(4) = 2 * 5 + 2 = 12, F(5) = 2 * 12 + 5 = 29.*


#### Вопрос 2: Какие утверждения о мемоизации верны?
- ✅ functools.lru_cache хранит результаты прошлых вызовов и отдаёт их при повторном запросе
- ✅ с lru_cache каждый конкретный fib(k) реально вычисляется не более одного раза
- ☐ декоратор lru_cache меняет саму формулу рекурсии
- ✅ без мемоизации число вызовов fib(n) растёт примерно как сами числа Фибоначчи

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


#### Вопрос 3: Функция fib задана наивно: fib(1) = 1; fib(2) = 1; fib(n) = fib(n - 1) + fib(n - 2). Сколько всего вызовов fib произойдёт при вычислении fib(6)? Считай и сам вызов fib(6). Запиши число.
**Ответ:** 15

*Пояснение: Число вызовов живёт по своей рекурсии: C(1) = C(2) = 1, дальше C(n) = C(n - 1) + C(n - 2) + 1: C(3) = 3, C(4) = 5, C(5) = 9, C(6) = 15.*


#### Вопрос 4: Расставь события трассировки f(3), где f(n) = 1 при n <= 1 и n * f(n - 1) иначе, в порядке их наступления.
**Правильный порядок:** вызов f(3): база не сработала, нужен f(2) → вызов f(2): снова рекурсивный шаг, нужен f(1) → f(1) срабатывает как база и возвращает 1 → f(2) получает 1 и возвращает 2 * 1 = 2 → f(3) получает 2 и возвращает 3 * 2 = 6

*Пояснение: Сначала вызовы погружаются: f(3), затем f(2). На f(1) срабатывает база, и значения возвращаются обратно: f(2) даёт 2, f(3) даёт 6.*


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

*Пояснение: Четыре опоры любой рекурсии: дно, шаг, учёт кадров стека и кэш против повторов.*


#### Вопрос 6: Разложи задачи по корзинам: где цикл справится честнее, а где рекурсия естественнее.
- **Цикл честнее:** сложить элементы списка, вывести числа от 1 до 100, средний балл по списку
- **Рекурсия естественнее:** обойти все вложенные папки, Ханойские башни, разобрать выражение со вложенными скобками

*Пояснение: Ровные данные одной размерности складываются в цикле, а вложенные структуры и самоподобные головоломки вроде Ханойских башен просятся в рекурсию.*


#### Вопрос 7: Дополни: рекурсивная функция опирается на ___ случай, а рекурсивный шаг каждый раз работает с задачей ___ размера. Если базы нет или до неё не добраться, Python упадёт с ошибкой ___.
Рекурсивная функция опирается на **базовый** случай, а рекурсивный шаг каждый раз работает с задачей **меньшего** размера. Если базы нет или до неё не добраться, Python упадёт с ошибкой **RecursionError**.

*Пояснение: База останавливает вызовы, шаг уменьшает задачу, а превышение лимита глубины стека даёт RecursionError.*


## Тренажёр

На [странице тренажёра](https://shkolniygid.ru/informatika/11-klass/rekursiya-python-11/trenazher/) — 4 типов задач с бесконечными вариантами чисел, проверкой ответа и разбором каждого шага.