Рекурсия в ЕГЭ по информатике: как вычислить функцию на Python и не упасть по глубине

21 октября 2026 г. · 3 мин чтения · Редакция Skill Unit

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

Шаг 1. Перепишите условие дословно

Условие обычно выглядит так: F(n) = n при n < 3; F(n) = F(n − 1) + 2·F(n − 2) при n ≥ 3. Найдите F(25). Главное правило: каждая строка условия становится строкой кода, порядок проверок тот же. Сначала базовый случай, потом общий.

def F(n):
    if n < 3:
        return n
    return F(n - 1) + 2 * F(n - 2)

print(F(25))

Программа выведет 16777216. Для проверки посчитайте вручную пару первых значений: F(1) = 1, F(2) = 2, F(3) = 2 + 2 = 4, F(4) = 4 + 4 = 8. Видна закономерность: значения удваиваются, и F(25) = 2²⁴ = 16 777 216. Совпадение ручной проверки с программой — лучший признак, что условие перенесено верно.

Шаг 2. Если считает слишком долго — добавьте кэш

Функция выше вызывает себя дважды, и число вызовов растёт очень быстро: для n около 40 программа может считать минутами. Причина в том, что одни и те же значения пересчитываются много раз. Решение — запоминать уже найденные значения. В Python для этого есть декоратор lru_cache из модуля functools.

from functools import lru_cache

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

print(F(100))

Теперь каждое значение считается один раз, и даже F(100) выводится мгновенно. Одна строка импорта и одна строка декоратора — запомните их как шаблон.

Шаг 3. Если ошибка RecursionError

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

• Поднять предел: import sys и sys.setrecursionlimit(10000). Помогает, если нужная глубина не слишком велика.
• Заполнить кэш снизу вверх: в цикле вызвать функцию для n = 1, 2, 3 и так далее до нужного. Каждый следующий вызов опирается на уже посчитанное значение, и глубина остаётся маленькой.

Пример: G(1) = 1, G(n) = G(n − 1) + n. Найдите G(3000) − G(2995).

from functools import lru_cache

@lru_cache(None)
def G(n):
    if n == 1:
        return 1
    return G(n - 1) + n

for i in range(1, 3001):
    G(i)

print(G(3000) - G(2995))

Ответ 14990. Проверка в уме: разность равна 2996 + 2997 + 2998 + 2999 + 3000 = 14 990. Обратите внимание: в таких задачах часто просят именно разность или частное, потому что сами значения огромные. Python работает с большими целыми числами без потери точности, так что считать «в лоб» можно.

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

• Перепутан порядок проверок: общий случай стоит раньше базового, и функция уходит в бесконечные вызовы.
• Строгое и нестрогое неравенство: «при n < 3» и «при n ≤ 3» дают разные ответы.
• Деление: если в условии целочисленное деление, пишите //, а не /, иначе получите дробь.
• Две функции, которые вызывают друг друга: обе нужно описать до первого вызова и обе закэшировать.
• Ответ не проверен на маленьких n: две-три строки ручного счёта ловят большинство опечаток.

Как тренироваться

Возьмите десять условий с рекурсией из открытого банка ФИПИ и для каждого сделайте три вещи: ручной расчёт для n = 1…4, программу без кэша, программу с кэшем. Через неделю шаблон будет писаться за минуту, а время на экзамене уйдёт на задачи, где нужно думать.

Рекурсию, перебор, работу с файлами и все остальные типы заданий разбирают в курсе «ЕГЭ по информатике» — с задачами на Python и мгновенной проверкой ответов.