16 задание ЕГЭ по информатике: рекурсия и как решать

Кому: выпускнику · Обновлено 2026-10-25

Раздел: Информатика · Тема: Разборы заданий по номерам · Задание 16

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

Решить задание в тренажёре

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

В задании № 16 дано начальное значение (или несколько) и правило, по которому каждое следующее значение выражается через предыдущие. Тебе нужно найти значение функции для конкретного аргумента. Ответ — одно число, часто очень большое, поэтому считать вручную нет смысла: проверяется умение перевести условие в программу.

Условия бывают трёх типов: функция зависит от одного предыдущего значения (F(n − 1)), от нескольких (F(n − 1) и F(n − 2)) или от значения, делённого пополам (F(n // 2)). Ещё часто встречаются ветвления: одно правило для чётных n, другое для нечётных, третье для n, кратных какому-то числу.

Актуальные требования к экзамену, число заданий и критерии смотри на сайте ФИПИ (fipi.ru) в спецификации и кодификаторе. Там же лежат демоверсии, по которым видно формат записи условия.

16 задание ЕГЭ по информатике: шаблон на Python

Для большинства условий подходит один и тот же каркас. Перенеси условие в код почти дословно — так меньше шансов ошибиться.

Порядок действий:

• Выпиши все базовые случаи: те значения, которые заданы напрямую, например F(1) = 1. Они идут в функции первыми, в начале, через if.
• Для каждого рекуррентного правила напиши отдельную ветку и сохрани условие, при котором оно действует (n > 1, n чётное и так далее).
• Внутри ветки замени F на вызов своей функции: def f(n): if n == 1: return 1, затем return f(n - 1) * 4 + 5.
• Сделай вызов print(f(21)) с аргументом из вопроса и скопируй результат в ответ целиком, без округления.
• Прогони функцию на малых n (1, 2, 3) и сверь с ручным подсчётом по условию.

Рекурсия и lru_cache: как не получить зависание

Если функция вызывает сама себя дважды (например, F(n − 1) + F(n − 2)), число вызовов растёт лавинообразно, и программа на n около 40 и больше может считаться очень долго. Одно и то же значение при этом пересчитывается много раз.

Решение — кэш. В Python подключается так: из модуля functools импортируй lru_cache и поставь строку @lru_cache(None) прямо над определением функции. Теперь каждое значение вычисляется один раз и запоминается, а программа отрабатывает мгновенно.

Вторая проблема — глубина рекурсии. По умолчанию Python допускает около тысячи вложенных вызовов. Если в условии n порядка нескольких тысяч, добавь в начало программы import sys и строку sys.setrecursionlimit(100000), либо переходи к решению через список.

16 задание через списки: рекуррентность без рекурсии

Когда функция зависит только от меньших аргументов, её можно считать циклом снизу вверх. Заведи список f, запиши в него базовые значения и заполняй дальше по правилу: for n in range(2, N + 1): f.append(f[n - 1] * 4 + 5).

Преимущества: нет ограничения на глубину, нет риска зависания, легко печатать промежуточные значения. Недостаток: нужно аккуратно выбрать индексацию. Если нумерация в условии начинается с единицы, добавь в список фиктивный нулевой элемент или сдвигай индексы осознанно.

Если в условии есть деление пополам (F(n // 2)), через список считать тоже можно, но удобнее оставить рекурсию с кэшем: порядок вычисления подберётся сам.

Задание с двумя функциями

Иногда в условии определены две функции, например F(n) и G(n), и каждая использует значения другой. Здесь шаблон остаётся тем же: пиши две функции в программе, обе с базовыми случаями, и разреши им вызывать друг друга. Python спокойно обрабатывает такую взаимную рекурсию, если обе функции описаны до первого вызова.

Кэш ставь над каждой из функций. Следи, чтобы базовые случаи были заданы для обеих: чаще всего ошибка в том, что для G забыли начальное значение, и программа уходит в бесконечную рекурсию.

Если нужно вычислить комбинацию, например F(20) − G(20), считай значения отдельными вызовами и вычитай уже в print.

Разбор руками: когда он нужен

Полностью считать вручную ответ из 12–13 цифр не нужно. Но руками полезно проверить первые два-три шага: это быстро ловит ошибки в базовых случаях и знаках.

Алгоритм проверки: подставь в условие n = 1, 2, 3 и получи значения на бумаге. Затем запусти программу на тех же аргументах. Если результаты расходятся, ошибка в условии if или в записи выражения, а не в самой идее.

Разбор «руками» бывает нужен и для вопросов вида «сколько раз вызовется функция» или «какое значение будет на шаге k». Тогда выпиши цепочку вызовов столбиком до базового случая.

Типичные ошибки и самопроверка

Большинство неверных ответов в этом задании вызвано не сложностью идеи, а мелкими неточностями при переносе условия в код. Перед отправкой ответа пройдись по списку:

• Перепутана граница: в условии n > 1, а в коде n >= 1, из-за чего базовый случай не срабатывает.
• Использовано деление / вместо целочисленного //: в ответе получается дробное число с точкой.
• Забыт базовый случай для второго начального значения, например F(2).
• Не подключён кэш, и программа считает дольше нескольких секунд.
• Не тот аргумент: в вопросе спрашивают F(21), а в print написано f(20).
• Ответ записан в экспоненциальной форме или округлён: нужно целое число полностью.
• Проверка: пересчитай то же значение вторым способом — рекурсией с кэшем и циклом со списком. Если числа совпали, ответ почти наверняка верный.

Как потренироваться

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

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

Материал — разъяснение «Ранг». Официальные правила экзамена, расписание, шкалы баллов и перечни заданий публикуют ФИПИ (fipi.ru) и Рособрнадзор (obrnadzor.gov.ru). Мы не обещаем конкретных баллов: результат зависит от твоей работы.