Перейти к содержимому

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

Задание 16до 1 балларекурсивные функции
Раздел
Алгоритмы и программирование
Максимальный балл
1 балл
Уровень
повышенный
Что проверяет
Вычисление рекуррентных выражений
Что нужно сделать
Вычислить значение рекуррентно заданной функции — программой с рекурсией или циклом.
Как записать ответ
только число: целое, без пробелов и единиц измерения
Время
Около 5 минут по обобщённому плану ФИПИ
Элемент кодификатора
3.7
Компьютер
Нужна программа или электронная таблица: на станции КЕГЭ — среды программирования на C#, C++, Pascal, Java, Python и редактор таблиц
Файл к заданию
Нет — все данные в условии
В 2026 году
Тоже задание 16
Решать варианты КЕГЭ целиком →Практика на этой странице ↓

Задание 16 ЕГЭ по информатике 2027 года проверяет, по формулировке обобщённого плана ФИПИ, «вычисление рекуррентных выражений» (код элемента содержания 3.7, требование 1.8). Функция F(n) задана через свои значения при меньших n, а спросить могут значение выражения с большими аргументами: в демоверсии это (F(3038) + 5 × F(3037)) / F(3036). Файла к заданию нет, но по обобщённому плану для него нужно специализированное ПО: значение считают программой, хотя конкретный пример демоверсии после сокращения сводится к произведению двух чисел.

Уровень — повышенный, по обобщённому плану около 5 минут, за верный ответ дают 1 балл, ответ — одно целое число. По методическим рекомендациям ФИПИ средний процент выполнения задания 16 составил 54,3 в 2025 году и 62,4 в 2026-м.

Изменений в 2027 году нет: «Изменения структуры КИМ отсутствуют», а смена тематики коснулась только заданий 10, 13 и 23. В 2026 году под этим номером было то же задание.

Ниже — три типа задания с разбором и решением на Python, код можно запустить прямо на странице. Разбор демоверсии 2027 года и типичные ошибки — дальше.

Тренажёр задания 16

Десять заданий номера 16 из банка тренажёра — с файлами, как на станции КЕГЭ. Решайте в песочнице Python прямо на странице или у себя; ответ проверяется по ключу, после проверки — верный ответ, разбор и решение на Python, а при ошибке — разбор от ИИ. Кнопка «Ещё 5 таких» у типа задания ниже даёт задания одного типа.

Загружаем задание…

Задание 16 вместе с остальными — в вариантах целиком.

Типы задания 16 с решением

Значение выражения с факториалами

Пример условия

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями:

F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1

Чему равно значение выражения (F(2820) + 3 × F(2819)) / F(2818)?

1. F(n) = n × F(n − 1) вместе с F(1) = 1 задаёт факториал: F(n) = n!. 2. Расписываем старшие значения: F(2820) = 2820 × 2819 × F(2818), F(2819) = 2819 × F(2818). 3. Сокращаем дробь на F(2818) — деление точное. 4. Остаётся 2820 × 2819 + 3 × 2819 = 2819 × (2820 + 3) = 2819 × 2823.

На примере: 2819 × 2823 = 7 893 200 + 64 837 = 7 958 037. Программа ниже обходит рекурсию циклом и берёт готовые значения из списка.

Решение на Python
# F(n) = n * F(n - 1) при F(1) = 1 — это факториал
N = 2820
F = [1] * (N + 1)          # F[0] = 1: с ним цикл записывается короче
for n in range(1, N + 1):
    F[n] = n * F[n - 1]

# берём готовые значения, а не три отдельных факториала
print((F[2820] + 3 * F[2819]) // F[2818])

Ответ: 7958037

Разность значений взаимно рекурсивных функций

Пример условия

Функции F(n) и G(n), где n — натуральное число, заданы соотношениями:

F(1) = 3;
G(1) = 1;
F(n) = 2 × F(n − 1) + 2 × G(n − 1) + 3 × n, если n > 1;
G(n) = F(n − 1) + 3 × G(n − 1) + n + 1, если n > 1

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

1. Функции взаимные: для F(n) нужен G(n − 1) и наоборот, по отдельности их не считают. 2. Обозначим D(n) = F(n) − G(n) и вычтем из равенства для F равенство для G: F(n − 1) и G(n − 1) сократятся, останется D(n) = D(n − 1) + 2n − 1. 3. Начальное значение D(1) = 3 − 1 = 2. 4. Суммируем приращения при n от 2 до 974: нечётные числа от 3 до 1947, их 973, сумма 973 × 975 = 948 675.

На примере: D(974) = 2 + 948 675 = 948 677. Сами F(974) и G(974) содержат сотни цифр, но в разности эти части сокращаются; программа ниже считает их целиком.

Решение на Python
# F и G взаимные: обходимся без рекурсии, считаем снизу вверх
N = 974
F = [0] * (N + 1)
G = [0] * (N + 1)
F[1], G[1] = 3, 1
for n in range(2, N + 1):
    F[n] = 2 * F[n - 1] + 2 * G[n - 1] + 3 * n
    G[n] = F[n - 1] + 3 * G[n - 1] + n + 1

print(F[N] - G[N])

Ответ: 948677

Число вызовов рекурсивной функции

Пример условия

Функция F(n), где n — натуральное число, задана соотношениями:

F(n) = 1, если n ≤ 2;
F(n) = F(n − 1) + F(n − 2), если n > 2

Сколько раз будет вызвана функция F при вычислении значения F(22), включая первый вызов?

1. Считают не значение функции, а число её вызовов — каждый заход в F, включая первый. 2. Вызов F(x) при x > 2 порождает вызовы F(x − 1) и F(x − 2), да ещё считается сам: C(x) = 1 + C(x − 1) + C(x − 2). 3. При x ≤ 2 вызов ровно один: C(1) = C(2) = 1 — начало счёта. 4. Идём по возрастанию x циклом. Запоминать значения функции нельзя: тогда исчезнут повторные вызовы, которые и нужно сосчитать.

На примере: C(20) = 13 529, C(21) = 21 891, C(22) = 1 + 21 891 + 13 529 = 35 421. Постоянные слагаемые в формуле значения на число вызовов не влияют.

Решение на Python
# считаем не значение F, а число вызовов для каждого аргумента
N = 22
calls = [1] * (N + 1)      # при n не больше 2 вызов ровно один
for n in range(3, N + 1):
    calls[n] = 1 + calls[n - 1] + calls[n - 2]

print(calls[N])

Ответ: 35421

Шаблон кода на Python

Рекурсивные функции

lru_cache запоминает значения, и рекурсия идёт быстро. Глубокую рекурсию считайте снизу вверх: так не упрётесь в предел глубины.

Python
from functools import lru_cache

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

for i in range(1, 3001):   # снизу вверх — без глубокой рекурсии
    F(i)
print(F(30) - F(28))
Вывод
8194

Шаблоны кода ко всем заданиям

Как выполнять задание

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

Что нужно знать

  • Рекуррентная функция. F(n) выражено через F от меньших аргументов, есть начальные условия — при n = 1, реже при n ≤ 2 или n ≤ 4.
  • Мемоизация. При F(n) = F(n − 1) + F(n − 2) число вызовов растёт как числа Фибоначчи: для n = 22 их 35 421. @lru_cache из functools запоминает ответы и сводит работу к N шагам.
  • Факториал. F(n) = n × F(n − 1) при F(1) = 1 — это F(n) = n!. Тогда F(n)F(n − 1) = n, F(n)F(n − 2) = n × (n − 1): факториалы сокращают, а не считают.
  • Цикл вместо рекурсии. Запись for n in range(2, N + 1): F[n] = … обходится без кэша и без sys.setrecursionlimit.
  • Большие целые. Числа здесь — тысячи цифр; деление всегда точное, поэтому пишут a // b.

Как оценивается

Проверка автоматическая, по ключу: ответ должен быть записан в форме из условия и полностью совпасть с эталоном. Код и черновики не проверяют — значение имеет только ответ. За верный ответ — 1 балл, частичного балла нет.

Критерии всех заданий экзамена — на странице критериев ЕГЭ.

Разбор задания демоверсии 2027

В демоверсии 2027 года функция задана так: F(n) = 1 при n = 1 и F(n) = n × F(n − 1) при n > 1, а найти нужно (F(3038) + 5 × F(3037)) / F(3036).

Разберём руками. Соотношение задаёт факториал, поэтому F(3038) = 3038 × 3037 × F(3036), а F(3037) = 3037 × F(3036). Сокращаем дробь на F(3036): остаётся 3038 × 3037 + 5 × 3037 = 3037 × 3043. Считаем по частям: 3037 × 3000 = 9 111 000, 3037 × 43 = 130 591, итого 9 241 591.

Ключ ФИПИ — 9 241 591. Столько же печатает программа того же вида, что в первом типе ниже, если взять в ней N = 3038 и коэффициент 5: цикл доводит значения до нужного n. Числа такой длины Python считает точно, а деление записывают как //.

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

Рекурсия без запоминания

Формула F(n) = F(n − 1) + F(n − 2) «в лоб» даёт два вызова на каждый вызов: для n = 22 их 35 421, а при n около 3000 счёт не завершится. Нужен @lru_cache или цикл снизу вверх.

RecursionError при большой глубине

Глубина рекурсии в Python по умолчанию около 1000 вызовов. Спуск до F(3038) из демоверсии её превышает: либо ставят sys.setrecursionlimit, либо обходятся циклом.

Деление / вместо //

3038! содержит тысячи цифр. Деление / переводит целые в вещественные и на таких числах падает. Здесь деление всегда точное, поэтому пишут a // b.

Неверные начальные значения

В одних условиях F(1) = 1, в других F(n) = 1 при n ≤ 2 или n ≤ 4. Не то основание — и дальше посчитается не та функция.

В задании на вызовы печатают значение функции

Когда спрашивают, сколько раз вызвана функция, нужен счётчик вызовов, а не результат F(22): вызовов 35 421, а само значение F(22) равно 17 711.

Вопросы и ответы

Как решать задание 16 ЕГЭ по информатике?

Если выражение сокращается, подставьте F от больших аргументов через младшие и посчитайте оставшееся произведение вручную. Если не сокращается — взаимные функции или подсчёт вызовов — пишите программу: с @lru_cache либо циклом снизу вверх.

Какой шаблон кода на Python подходит для задания 16?

Счёт снизу вверх: список F длиной N + 1, начальные значения F[1] и F[2], затем for n in range(3, N + 1): F[n] = … по формуле из условия, в конце печать ответа. Вариант с @lru_cache короче, но при больших n требует поднять лимит рекурсии.

Сколько баллов даёт задание 16 и сколько на него времени?

1 балл: задания 1–25 оцениваются одним баллом. По обобщённому плану ФИПИ отводится около 5 минут, уровень — повышенный. Ответ должен полностью совпасть с эталоном.

Что изменилось в задании 16 в 2027 году?

Ничего. В спецификации сказано: «Изменения структуры КИМ отсутствуют», а тематику сменили только у заданий 10, 13 и 23. Задание 16 в оба года проверяет вычисление рекуррентных выражений и предполагает использование программы.

Другие задания раздела «Алгоритмы и программирование»

По демоверсии, спецификации и кодификатору ФИПИ 2027
Обновлено:

Все задания ЕГЭ по информатике →