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

В задании 16 ЕГЭ по информатике функция задана через саму себя: F(n) выражается через F(n + 2) или F(n − 1), а для крайних n дано готовое значение. Спрашивают значение выражения с этой функцией. На Python условие переписывается почти дословно — функцией с def. Подвох в глубине: цепочка вызовов бывает длиннее 1000, и тогда Python останавливает программу. Примеры ниже запускаются прямо на странице и составлены для этой статьи: на экзамене функции и числа будут другими, а приёмы — те же.

ЕГЭ / 01koddo

F(14) ждёт F(16), та — F(18), и так до F(3000)

Пример задачи

Функция F(n) задана так:

• F(n) = n при n ≥ 3000;
• F(n) = n + 2 + F(n + 2) при n < 3000.

Чему равно значение выражения F(14) − F(18)?

Решение

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n >= 3000:
        return n
    return n + 2 + F(n + 2)

print(F(14) - F(18))

34

• Функция повторяет условие: сначала случай без рекурсии (n ≥ 3000), потом — через F(n + 2).
• F(14) вызывает F(16), та — F(18), и так до F(3000): 1 494 вызова один в другом. По умолчанию Python разрешает глубину 1000, поэтому sys.setrecursionlimit(10000) поднимает предел с запасом.

Ответ: 34.

Проверка сокращением. F(14) = 14 + 2 + F(16) = 16 + F(16), а F(16) = 18 + F(18). Значит, F(14) − F(18) = 16 + 18 = 34, и до 3000 доходить не нужно.

Что будет без setrecursionlimit

def F(n):
    if n >= 3000:
        return n
    return n + 2 + F(n + 2)

print(F(14) - F(18))

Python остановит программу с ошибкой RecursionError: maximum recursion depth exceeded: цепочка из 1 494 вызовов длиннее разрешённой. Предел ставят с запасом над глубиной цепочки — здесь 10 000 хватает.

Большие числа

Другой вид: F(n) = 1 при n = 1 и F(n) = n · F(n − 1) при n > 1. Чему равно значение выражения (F(2024) + 2 · F(2023)) / F(2022)?

import sys
sys.setrecursionlimit(10000)

def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)

print((F(2024) + 2 * F(2023)) // F(2022))

4098598

F(n) здесь — факториал n!, и в F(2024) 5 815 цифр. Python хранит целые числа любой длины и делит их точно, поэтому // даёт ответ без потерь.

Проверка сокращением. F(2024) = 2024 · 2023 · F(2022), а F(2023) = 2023 · F(2022). После деления на F(2022) остаётся 2024 · 2023 + 2 · 2023 = 2023 · 2026 = 4 098 598.

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

Нет setrecursionlimit. Цепочка длиннее 1000 вызовов останавливается с RecursionError, как в примере выше.

Печать огромного числа. print(F(2024)) останавливается с ошибкой ValueError: Exceeds the limit (4300 digits) for integer string conversion: Python не переводит в строку целые числа длиннее 4300 цифр. Печатать такое число и не нужно — после сокращения ответ небольшой. Если всё же нужно, предел снимает sys.set_int_max_str_digits(0).

/ вместо //. Обычное деление даст 4098598.0 — дробное число, а ответ в задании целый.

Две ветки рекурсии без кэша. Если F(n) выражается через F(n − 1) и F(n − 2), одни и те же значения считаются заново, и программа не закончится. Нужен lru_cache — пример в статье «Python для ЕГЭ по информатике».

Теория игр из заданий 19–21 решается такой же рекурсией — в статье «Задания 19–21 ЕГЭ на Python». Свой вариант удобно проверять в песочнице Python: пошаговое выполнение покажет, как вызовы уходят вглубь и возвращаются.