Задание 16 ЕГЭ по информатике: вычисление рекуррентных выражений
Задание 16 ЕГЭ по информатике проверяет вычисление рекуррентных выражений: функция задана через саму себя, и нужно найти её значение или значение выражения из нескольких вызовов. Прямой рекурсивный вызов на Python часто упирается в ограничение глубины, поэтому значения считают циклом или сначала упрощают выражение на бумаге.
- Что проверяет: Вычисление рекуррентных выражений. Функция F(n) задаётся базовым значением и формулой, которая выражает F(n) через значения при других аргументах.
- Баллы: 1 первичный балл
- Формат ответа: Целое число
- Программа: задание решают программой
- Уровень сложности: повышенный
- Время: около 5 минут по спецификации
- Кодификатор: 3.7 — рекурсия; рекурсивные процедуры и функции; использование стека для организации рекурсивных вызовов; требование 1.8 — владение теоретическим аппаратом, позволяющим осуществлять представление заданного натурального числа в различных системах счисления; выполнять преобразования логических выражений
Как решать
Функцию из условия переписывают на Python почти дословно: базовый случай — через if, рекуррентная формула — через return с вызовом той же функции. Для небольших n этого достаточно.
Для больших n, в тысячи и больше, прямой вызов даёт ошибку RecursionError: по умолчанию Python допускает около тысячи вложенных вызовов. Есть три выхода. Первый — считать значения по порядку в цикле и хранить их в словаре или списке. Второй — поднять предел через sys.setrecursionlimit и вызывать функцию для возрастающих n, чтобы заполнить кэш lru_cache. Третий — упростить выражение вручную.
Упрощение на бумаге часто короче программы. Если F(n) = n·F(n − 2), то F(2026) = 2026·2024·F(2022), и в отношении к F(2022) огромные числа сокращаются. Если F(n) = 2n + F(n + 3), то разность F(41) − F(47) равна сумме двух первых слагаемых.
Для заданий вида «сколько существует n, для которых F(n) = k» считайте значения функции списком для всех n подряд: каждое следующее значение опирается на уже вычисленные. Целочисленное деление в формулах записывайте через //: деление / даёт дробное число и при больших значениях теряет точность.
Примеры с решением
Пример 1
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
- F(n) = n при n ≤ 2;
- F(n) = n × F(n − 2), если n > 2.
Чему равно значение выражения (F(2026) − F(2024)) / F(2022)?
Решение на Python
F = {1: 1, 2: 2}
for n in range(3, 2027):
F[n] = n * F[n - 2]
print((F[2026] - F[2024]) // F[2022])Ответ: 4098600
По формуле F(2026) = 2026 × 2024 × F(2022) и F(2024) = 2024 × F(2022). Значит, (F(2026) − F(2024)) / F(2022) = 2026 × 2024 − 2024 = 2024 × 2025 = 4 098 600. Программа считает значения циклом от 3 до 2026: прямая рекурсия здесь потребовала бы больше тысячи вложенных вызовов.
Пример 2
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
- F(n) = n при n ≥ 3000;
- F(n) = 2 × n + F(n + 3), если n < 3000.
Чему равно значение выражения F(41) − F(47)?
Решение на Python
F = {}
for n in range(3002, 3000 - 1, -1):
F[n] = n # при n >= 3000 значение задано явно
for n in range(2999, 40, -1):
F[n] = 2 * n + F[n + 3]
print(F[41] - F[47])Ответ: 170
Распишем формулу на два шага: F(41) = 82 + F(44) = 82 + 88 + F(47). Поэтому F(41) − F(47) = 82 + 88 = 170. Программа идёт от больших n к меньшим: сначала значения при n ≥ 3000, затем F(2999), F(2998) и так далее до 41.
Пример 3
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
- F(0) = 0;
- F(n) = F(n − 1) + 1, если n нечётно;
- F(n) = F(n / 2) + 2, если n > 0 и n чётно.
Сколько существует натуральных чисел n, не превышающих 10 000, для которых F(n) = 12?
Решение на Python
F = [0] * 10001
for n in range(1, 10001):
if n % 2 == 1:
F[n] = F[n - 1] + 1
else:
F[n] = F[n // 2] + 2
print(sum(1 for n in range(1, 10001) if F[n] == 12))Ответ: 9
Список значений заполняется от 1 до 10 000: для нечётного n нужен F(n − 1), для чётного — F(n // 2), и оба уже вычислены. Подсчёт даёт 9. Тот же ответ получается рассуждением: F(n) равно числу единиц в двоичной записи n плюс удвоенная длина записи без одного. Значение 12 дают шестизначные двоичные числа с двумя единицами (их 5) и пятизначные с четырьмя единицами (их 4).
Типичные ошибки
- Вызывают рекурсию для n порядка тысяч без `sys.setrecursionlimit` и получают RecursionError.
- Поднимают предел рекурсии слишком высоко, и программа завершается аварийно без сообщения; надёжнее считать значения циклом.
- Используют деление `/` вместо `//` и получают дробное число вместо целого.
- Считают значения не в том порядке: если F(n) выражается через F(n + 3), идти нужно от больших n к меньшим.
Потренироваться на тренажёре
Частые вопросы
Почему программа с рекурсией выдаёт RecursionError?
Python по умолчанию ограничивает глубину вложенных вызовов примерно тысячей. Считайте значения циклом или поднимите предел командой `sys.setrecursionlimit` и заполняйте кэш вызовами для возрастающих n.
Можно ли решить задание 16 без программы?
Часто да: выражение из нескольких вызовов сокращается, если расписать рекуррентную формулу на один-два шага. Программа нужна для проверки и для заданий на подсчёт количества n.
Официальные материалы
Другие задания
Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 15 и задание 17.
Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.