Задание 16 ЕГЭ по информатике: рекурсивные функции — разбор и примеры

В задании 16 функция задана рекуррентно: несколько начальных значений и правило, по которому F(n) выражается через значения функции от других аргументов. Нужно найти значение функции при заданном n или значение выражения, например разность F(2024) − F(2020). Формально это вычисление по формуле, но на практике мешают две проблемы: экспоненциальное число вызовов и превышение глубины рекурсии в Python. Обе решаются стандартными приёмами, которые стоит выучить заранее.

Что проверяет задание

• умение читать рекуррентное определение: базовые случаи и шаг рекурсии;
• умение записать функцию на Python без ошибок в условиях;
• знание приёмов мемоизации (functools.lru_cache) и итеративного вычисления;
• понимание, как работать с глубокой рекурсией: sys.setrecursionlimit или «телескопическое» сокращение разности.

Типичные формулировки

1. «Алгоритм вычисления функции F(n) задан соотношениями: F(n) = 2 при n ≤ 2; F(n) = F(n − 1) + F(n − 2) + n при n > 2. Чему равно значение F(40)?»
2. Функция с ветвлением по чётности: разные формулы для чётных и нечётных n.
3. Разность при большой глубине: «G(n) = 2n при n ≥ 3000; G(n) = G(n + 3) + n − 1 при n < 3000. Найдите G(15) − G(21)».
4. Две взаимно рекурсивные функции F и G, вызывающие друг друга.

Пошаговый метод

1. Перепишите определение на Python дословно, сохранив порядок проверок. Базовые случаи — первыми.
2. Оцените число вызовов. Если F(n) вызывает себя дважды (как в примере 1), без запоминания число вызовов растёт как числа Фибоначчи: для n = 40 это сотни миллионов вызовов.
3. Добавьте @lru_cache(None) — каждое значение будет вычисляться один раз.
4. Если аргумент идёт вверх или вниз на тысячи шагов, увеличьте лимит рекурсии sys.setrecursionlimit(10000) или вычисляйте значения циклом от базового случая.
5. Для разности F(a) − F(b) попробуйте выразить F(a) через F(b): часто нужные слагаемые сокращаются, и ответ находится без огромных вычислений.

Разбор примера 1

F(n) = 2 при n ≤ 2; F(n) = F(n − 1) + F(n − 2) + n при n > 2. Найдите F(40).

Прямая рекурсия без запоминания работает очень долго: F(40) вызывает F(39) и F(38), каждая из них — ещё по две и так далее. Зато значения легко посчитать по порядку: F(3) = 2 + 2 + 3 = 7, F(4) = 7 + 2 + 4 = 13, F(5) = 13 + 7 + 5 = 25, F(6) = 25 + 13 + 6 = 44 и т. д. Продолжая до n = 40 (это делает программа), получаем F(40) = 677250873.

Разбор примера 2

G(n) = 2n при n ≥ 3000; G(n) = G(n + 3) + n − 1 при n < 3000. Найдите G(15) − G(21).

Здесь вычисление G(15) требует почти тысячи вложенных вызовов: 15, 18, 21, …, 3000. Стандартный лимит рекурсии Python (1000) может не хватить. Но разность можно найти без вычисления самих значений:

• G(15) = G(18) + 15 − 1 = G(18) + 14;
• G(18) = G(21) + 18 − 1 = G(21) + 17.

Значит, G(15) = G(21) + 14 + 17, и G(15) − G(21) = 31. Такой приём называют телескопическим сокращением: все «хвосты» рекурсии одинаковы и взаимно уничтожаются.

Код на Python

import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

print(F(40))            # 677250873

def G(n):
    if n >= 3000:
        return 2 * n
    return G(n + 3) + n - 1

print(G(15) - G(21))    # 31

Тот же пример 1 без рекурсии — циклом. Этот вариант не зависит от лимита рекурсии вообще:

a, b = 2, 2           # F(1), F(2)
for n in range(3, 41):
    a, b = b, a + b + n
print(b)              # 677250873

Если функция вызывается для очень больших аргументов последовательно (например, F(5000)), а значения нужны «снизу вверх», полезно предварительно заполнить кеш в цикле: for i in range(1, 5001): F(i). Тогда каждый вызов углубляется всего на пару уровней.

Взаимная рекурсия и строковые функции

Иногда в условии две функции, которые вызывают друг друга, например: F(n) = G(n − 1) + 1, G(n) = F(n − 2) · 2, и у каждой свои базовые случаи. На Python это записывается так же естественно: две функции def F(n) и def G(n), обе с @lru_cache(None). Python разрешает вызывать функцию, которая объявлена ниже в файле, — главное, чтобы к моменту вызова она уже была определена. Порядок объявления в этом случае не важен.

Встречается и вариант, где функция возвращает не число, а строку или выводит символы на экран («что напечатает вызов F(4)?»). Тогда удобно не печатать, а возвращать строку и склеивать результаты: так проще посчитать, например, сумму всех напечатанных чисел или количество выводов. При ручном решении таких задач рисуйте дерево вызовов: каждый узел — вызов функции с конкретным аргументом, листья — базовые случаи. Это же дерево помогает понять, почему без запоминания программа работает медленно: одинаковые поддеревья вычисляются снова и снова.

Частые ошибки

• Путают порядок условий: если базовый случай «n ≥ 3000» проверить после шага рекурсии, функция никогда не остановится.
• Не добавляют мемоизацию и ждут результата минутами, хотя с lru_cache ответ мгновенный.
• Получают RecursionError и считают, что задача «не решается»: увеличьте лимит или перейдите к циклу.
• Используют / вместо // в определениях с делением: результат становится вещественным и теряет точность.
• Ошибаются в разности: вычитают в обратном порядке или путают знак при телескопическом сокращении.
• Неверно записывают условие чётности: n % 2 == 0 — чётное число.

Потренируйтесь

Решите задачи на вычисление, разность и взаимную рекурсию: задания № 16 в банке. Отработать рекурсивный код можно на задачах с проверкой кода. Подробнее о вызовах и деревьях рекурсии — в статье «Рекурсивные функции». Следующая тема — задание 17: обработка последовательности чисел.