Продвинутый синтаксис Время: 5-10 мин def functools.lru_cache sys.setrecursionlimit

Рекурсия, глубина стека и lru_cache

Тема: Функции с возвратом значений, sys.setrecursionlimit и мемоизация @lru_cache

Рекурсия — основа Заданий №16 (Вычисление рекуррентных функций), №19–21 (Теория игр) и №23 (Динамика траекторий).

1. Ограничение глубины рекурсии (RecursionError)

По умолчанию в Python максимальная глубина рекурсии равна 1000. Если функция вызывается для $N=4000$, программа завершится ошибкой. Чтобы снять лимит:

import sys
sys.setrecursionlimit(100000)

2. Декоратор @lru_cache(None)

Если рекурсивная функция делает несколько ветвлений (например, $F(n) = F(n-1) + F(n-2)$), без кэша она будет работать экспоненциально долго $O(2^n)$. Добавление @lru_cache(None) сохраняет результаты вычислений в памяти, ускоряя функцию до $O(n)$:

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n <= 2: return 1
    return F(n-1) + F(n-2)

Разновидности и прототипы задания на экзамене

1. Базовые рекурсивные функции (Задание 16)

Перевод математической системы рекуррентных уравнений в код Python.

2. Мемоизация через @lru_cache(None)

Кэширование уже вычисленных значений для ускорения работы в миллионы раз.

3. Увеличение глубины рекурсии sys.setrecursionlimit

Снятие ограничения в 1000 вызовов для работы с n=5000+.

Боевой шаблон решения на Python

Запустить код в онлайн-песочнице

Боевой шаблон решения на Python

# === Шпаргалка: Шаблон рекурсии для ЕГЭ 16, 23, 19-21 ===
import sys
from functools import lru_cache

# Снимаем лимит глубины стека:
sys.setrecursionlimit(50000)

# 1. Задание 16 ЕГЭ:
@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + F(n - 1)
    else:
        return 2 * F(n - 2)

print("F(2026) =", F(2026))

# 2. Задание 23 ЕГЭ (Количество программ от A до B):
def count_ways(curr, target):
    if curr == target: return 1
    if curr > target or curr == 13: return 0 # 13 — избегаемое число
    return count_ways(curr + 1, target) + count_ways(curr * 2, target)

print("Путей от 1 до 20:", count_ways(1, 20))

Типичные ошибки

✕ Не так

# ❌ Ошибка: Забыть базовый случай выхода из рекурсии

def F(n): return F(n-1) + 1 # Бесконечная рекурсия -> RecursionError!

✓ Так

# ✅ Правильно: Всегда указывать условие остановки (if n == 1: return ...)

ГРОБ

ЛОВУШКА: Превышение стека даже с lru_cache при прямом вызове F(5000)

Если вызвать F(5000) сразу, стек может переполниться до того, как кэш заполнится.

Как обойти

Прогрейте кэш циклом снизу вверх: for i in range(1, 5001): F(i).

Лайфхаки на экзамене

Всегда импортируйте from functools import lru_cache и вешайте @lru_cache(None) на функцию №16!
Для Задания 23 рекурсия с двумя вызовами пишется ровно в 4 строчки.

Все разборы заданий Открыть в тренажере СмартКИМ