Задание 16: Рекурсивные функции

Теория к заданию № 16 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

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

Что проверяет
Умение вычислять рекуррентные выражения: значения функции, заданной через саму себя, и выражения из таких значений при больших аргументах.
Баллы
до 1 балл из 29 первичных
Уровень
повышенный
Время
около 5 минут (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат
краткий ответ; нужен компьютер (программа, таблица или файл)

Правило и теория

  • Рекурсивная функция определяется базой (F(n) при малых n) и переходом (F(n) через F(n − 1), F(n − 2) …).
  • Прямой рекурсивный вызов для больших n упирается в глубину стека: используй sys.setrecursionlimit и @lru_cache или считай циклом снизу вверх.
  • Выражения вида F(2025) − F(2023) часто упрощаются аналитически: распиши переход и сократи общие части.
  • Если функций две (F и G), вычисляй их в одном цикле по возрастанию n.
  • Проверяй условия перехода точно как в задании: «n < 28», «n ≥ 28», «n чётно».

Приём решения по шагам

  1. Перепиши определение на Python один в один.
  2. Если n большой — добавь кэш и увеличь предел рекурсии или замени на цикл.
  3. Посчитай требуемое выражение (целые числа Python — без переполнения).
  4. При сомнениях проверь на маленьком n вручную.

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 3 × n + 1, если n < 28; F(n) = F(n − 4) + 4, если n ≥ 28 и n чётно; F(n) = F(n − 2) + 2, если n ≥ 28 и n нечётно. Чему равно значение выражения F(10671) − F(10664)?

Показать ответ и разбор

Ответ: 13

1) Шаг уменьшения чётный, поэтому чётность аргумента при спуске сохраняется: чётный аргумент всё время идёт по первой ветке, нечётный — по второй. 2) F(10671): 5322 шагов по −2 до аргумента 27 < 28; F(27) = 82, F(10671) = 82 + 2·5322 = 10726. 3) F(10664): 2660 шагов по −4 до аргумента 24 < 28; F(24) = 73, F(10664) = 73 + 4·2660 = 10713. 4) F(10671) − F(10664) = 10726 − 10713 = 13. Ответ: 13

Карточка банка «Ранга» informatics-16-0 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями: F(n) = 3 × (G(n − 5) − 1802); G(n) = 2 × n, если n < 25; G(n) = G(n − 4) + 1, если n ≥ 25. Чему равно значение выражения F(8 393)?

Показать ответ и разбор

Ответ: 1011

1) F(8393) = 3 × (G(8388) − 1802). 2) Пока аргумент не меньше 25, G уменьшает его на 4 и прибавляет 1. От 8388 до первого аргумента меньше 25 шагов j = 2091: 8388 − 4·2091 = 24. 3) G(24) = 2·24 = 48, значит G(8388) = 48 + 1·2091 = 2139. 4) F(8393) = 3 × (2139 − 1802) = 1011. 5) Программой: рекурсия здесь глубиной около 2091 вызовов — больше стандартного предела Python (1000), поэтому подними sys.setrecursionlimit или считай G циклом снизу вверх; оба способа дают то же значение. Ответ: 1011

Карточка банка «Ранга» informatics-16-1 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

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

  • Путают строгое и нестрогое неравенство в условии перехода.
  • Используют деление / вместо целочисленного // — получают дробные значения.
  • Программа без кэша считает «вечно» — нужен lru_cache или цикл.
  • Берут значения не той функции (F вместо G).

Тренироваться: 30 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 16

Кабинет ученика · Разбор задания 16: 10 примеров

Частые вопросы о задании 16

Сколько баллов дают за задание 16 ЕГЭ по информатике?
До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.
Сколько времени тратить на задание 16?
Примерное время выполнения по спецификации ФИПИ — 5 минут; на весь экзамен отводится 235 минут.
Что проверяет задание 16?
Умение вычислять рекуррентные выражения: значения функции, заданной через саму себя, и выражения из таких значений при больших аргументах.
Где потренироваться на задании 16?
В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.