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

Задание 16 ЕГЭ по информатике (КЕГЭ) — это функция F(n), заданная рекуррентно: несколько веток по чётности или диапазону аргумента, и вопрос «чему равно F(N)» для довольно большого N. По кодификатору это проверяемый элемент содержания 3.7 («Вычисление рекуррентных выражений»), задание повышенного уровня сложности, за него дают 1 первичный балл. Требуется среда программирования, но входного файла к заданию не прилагается — вся функция целиком дана в условии. Ответ — число. В статье — как читать рекуррентное определение, когда хватает таблицы «снизу вверх», рабочий шаблон рекурсии на Python, которая переписывает условие один в один, обязательные приёмы sys.setrecursionlimit и functools.lru_cache, поиск закономерности для сверхбольших N и три разбора реальных заданий из открытого банка ФИПИ с проверенными ответами. Потренироваться можно на реальных заданиях 16 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.

Что проверяет задание 16 ЕГЭ по информатике

Раздел кодификатора — «Алгоритмы и программирование», проверяемый элемент содержания 3.7 («Вычисление рекуррентных выражений»), проверяемое требование 1.8. Функция задаётся не формулой, а набором правил: одно или несколько «стартовых» значений (база рекурсии) и одно или несколько правил, которые выражают F(n) через значения функции при меньших аргументах (рекуррентный переход). Аргумент N, для которого нужно найти F(N), обычно исчисляется тысячами — вручную по цепочке от базы до N дойти нереально, а сама функция почти всегда растёт слишком быстро для формулы «в одну строчку», которую можно было бы просто подставить.

Проверяемые умения (КЭС 3.7, требование 1.8):

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

Параметр	Значение
Максимальный балл	1 первичный (частичного зачёта нет: ответ либо полностью совпал с эталоном, либо 0)
Уровень сложности	Повышенный (П) — одно из 11 заданий этого уровня в работе
Формат ответа	Краткий: одно число, без пробелов и разделителей
Раздел кодификатора	3. Алгоритмы и программирование; КЭС 3.7; требование 1.8
Нужен ли файл / спец. ПО	Требуется среда программирования, но входного файла к заданию нет — вся функция дана прямо в условии
Примерное время выполнения	5 минут (Обобщённый план варианта КИМ, СПЕЦ ЕГЭ-2026 по информатике)
Связанные задания	Задание 17 (тоже требует среду программирования, но с файлом на входе), задание 25 (тоже среда программирования без файла), задания 5, 6 и 23 (формальное исполнение и анализ хода алгоритма, КЭС 3.3)

Тренируйтесь на реальных заданиях

Задания 16 ЕГЭ по информатике из открытого банка ФИПИ с мгновенной проверкой ответа. Решаем, ошибаемся, разбираем — бесплатно.

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

Как выглядит формулировка

Условие задания 16 всегда построено по одной схеме: сначала текстом или формулой описывается функция F(n) — сколько у неё веток, что происходит в каждой, — а потом задаётся вопрос про конкретное значение или выражение из нескольких значений функции. Вот реальные формулировки из открытого банка ФИПИ:

«Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n > 1. Чему равно значение выражения (F(2024) − F(2023)) / F(2022)?»
«Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n — чётно; F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно. Чему равно значение функции F(26)?»
«Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 1 при n = 2; F(n) = 3 + F(n − 1), если n > 2 и при этом если n чётно; F(n) = 2 · n + F(n − 2), если n > 2 и при этом n нечётно. Чему равно значение функции F(42)?»
«Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1 при n < 3; F(n) = F(n − 1) + F(n − 2), если n > 2 и при этом n нечётно; F(n) = сумма F(i) по i от 1 до n − 1, если n > 2 и при этом n чётно. Чему равно значение функции F(24)?»

Обратите внимание на две устойчивые детали формулировки. Во-первых, база рекурсии в условии почти всегда стоит первой строкой («F(n) = 1 при n = 1»), а ветки перехода — после неё, но при чтении программы их обычно удобнее проверять в обратном порядке: сначала база, потом самое узкое условие. Во-вторых, вопрос не обязательно спрашивает про само F(N) — часто это выражение из нескольких значений функции сразу: разность, частное, сумма степеней или комбинация F(2024), F(2023) и F(2022) одновременно. Отвечать нужно на выражение целиком, а не на промежуточное F(N).

Как записывается ответ. Ответ на задание 16 — это одно число, целое, без пробелов и других разделителей между разрядами. Значения функции в этих заданиях быстро становятся многозначными (в примерах ниже встречаются ответы из 7 и 13 цифр) — это нормально, «некрасивое» большое число не повод пересчитывать заново. Единиц измерения, знаков вроде «=» и пояснений в ответе быть не должно — только число, которое затем целиком заносится в бланк.

Теория: как решать задание 16

Как читать рекуррентное определение

В определении функции F(n) всегда есть ровно два вида строк, и их нельзя путать местами.

База рекурсии — готовые значения без вычислений

Например, «F(n) = 1 при n = 1» или «F(n) = 1 при n <= 2». Это не формула, а факт: при таком n значение известно сразу, вызывать функцию рекурсивно не нужно. Баз может быть несколько — например, отдельно для n = 1 и для n = 2, если переход уменьшает аргумент сразу на 2.

Рекуррентный переход — правило через меньшие значения

Например, «F(n) = n × F(n − 1), если n > 1». Правая часть всегда содержит саму функцию F от аргумента, который меньше n — обычно n − 1 или n − 2. Именно убывание аргумента гарантирует, что цепочка вызовов рано или поздно дойдёт до базы и не зациклится.

Порядок веток — условия читаются как цепочка «если … иначе, если …»

Когда переходов несколько (по чётности, по остатку от деления на 3, по диапазону n), ветки в условии соответствуют друг другу как if / elif / elif в программе, а не как независимые формулы. Проверять их нужно в том порядке, в котором можно однозначно определить, какая ветка сработает для конкретного n — обычно это сначала база (самые маленькие n), затем всё более широкие условия. Авторы заданий формулируют ветки так, чтобы для каждого n подходила ровно одна, но убедиться в этом — ваша задача при чтении условия, а не что-то, что можно считать само собой разумеющимся.

Возьмём условие из первого примера этой статьи: «F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n — чётно; F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно». Здесь одна база (n = 1) и две ветки перехода — по чётности. Чтобы найти F(26): 26 чётно → переход к F(25); 25 нечётно и больше 1 → переход к F(23); и так далее, пока аргумент не станет равен 1.

Прямое вычисление «снизу вверх»: таблица значений

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

N = 26
F = [0] * (N + 1)
F[1] = 1
for n in range(2, N + 1):
    if n % 2 == 0:
        F[n] = n + F[n - 1]
    else:
        F[n] = 2 * F[n - 2]

print(F[N])

Этот способ работает всегда, когда N помещается в память — а для задания 16 это верно почти неизменно: даже таблица на несколько миллионов чисел считается меньше секунды. У него нет проблем с глубиной рекурсии в принципе, потому что рекурсии в нём нет вообще — только цикл. Единственное, за чем нужно следить: если в условии переход всегда уменьшает n на 2 (а не на 1, как в примере выше), в определении обычно и заданы две базы — для n = 1 и для n = 2 — потому что чётные и нечётные n тогда образуют две независимые цепочки. Заполните в массиве обе базы заранее, иначе одна из цепочек останется без стартового значения.

Слабое место у таблицы одно: если в переходе есть сумма по всем предыдущим значениям (как в примере с F(24) из блока формулировок, где для чётных n нужно сложить F(1) + … + F(n − 1)), наивный проход даёт квадратичное по n число действий. Для n в пределах пары тысяч это по-прежнему доли секунды, так что для задания 16 таблица остаётся рабочим способом и в этом случае.

Рекурсия на Python — самый надёжный путь

Таблица требует один раз аккуратно продумать порядок заполнения. Рекурсия проще: функцию на Python можно написать строчка в строчку по условию, вообще не думая о порядке вычислений — за него отвечает сам интерпретатор. Возьмём то же условие: «F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно; F(n) = 2 × F(n − 2), если n > 1 и нечётно». Переписываем один в один:

def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + F(n - 1)
    return 2 * F(n - 2)

print(F(26))

Каждая ветка условия стала строкой if, каждое обращение к F в правой части — рекурсивным вызовомF(...). Ничего сверх текста задания добавлять не нужно. Такой перевод «один в один» — самая надёжная защита от ошибки: если в условии три ветки, в функции должно быть ровно три проверки, и в том же порядке, что и в условии.

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

Глубина рекурсии и мемоизация — два разных ограничения

Проблема 1. Глубина рекурсии. По умолчанию Python обрывает цепочку вызовов после ~1000 уровней и выдаёт RecursionError. F(26) из примера выше эту границу не заденет, а вот F(2024) для функции F(n) = n × F(n − 1) — уже нет: цепочка идёт от 2024 до 1, это больше 1000 вложенных вызовов. Проверено: без изменения лимита F(2024) прямо падает с ошибкой. Решение — поднять лимит в самом начале программы:

import sys
sys.setrecursionlimit(100000)

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

print(F(2024) // F(2023))

После sys.setrecursionlimit(100000) цепочка вызовов глубиной 2024 проходит без ошибок. Это правило стоит применять по умолчанию в любой программе к заданию 16 — лишним оно не будет, даже если конкретное N окажется небольшим. Обратите внимание: печатается не само F(2024) (это число из тысяч цифр — 2024! — и современный Python откажется напечатать его целиком без отдельной настройки), а частное F(2024) // F(2023), которое равно 2024 и умещается в пару символов. Это ещё один довод в пользу приёма из следующего блока: удобнее находить закономерность и печатать итоговое небольшое число, чем выводить на экран промежуточные гиганты.

Проблема 2. Повторные вычисления. Она возникает у другого типа функций — там, где переход обращается к F сразу от двух предыдущих значений, например F(n) = F(n − 1) + F(n − 2) (числа Фибоначчи и похожие на них конструкции из банка). Без сохранения результатов дерево вызовов растёт экспоненциально: каждый вызов порождает два новых, и одни и те же значения пересчитываются заново тысячи раз. Вот замер на обычной наивной рекурсии Фибоначчи — без единой оптимизации, только само дерево вызовов:

import time

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

for n in (30, 32, 34):
    t = time.time()
    fib(n)
    print(n, round(time.time() - t, 3), "с")

# 30 0.089 с
# 32 0.253 с
# 34 0.655 с

Каждые +2 к n примерно утраивают время счёта — рост экспоненциальный. В заданиях банка N измеряется тысячами, и функция с двумя рекурсивными вызовами без оптимизации на таком N попросту не досчитается за разумное время. Решение — мемоизация: запоминать результат каждого F(n) при первом вычислении и отдавать готовое значение при повторном обращении. Проще всего — декоратор functools.lru_cache:

import sys
from functools import lru_cache

sys.setrecursionlimit(100000)

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

print(F(42))

Итоговое правило простое: sys.setrecursionlimit в начало программы — всегда; @lru_cache(maxsize=None) над функцией — всегда, если только вы не уверены, что переход ссылается ровно на одно предыдущее значение и повторных вычислений в принципе не возникает. Лишней мемоизация не бывает: она не портит правильный ответ, а только ускоряет счёт.

Когда N слишком велико даже для мемоизации: ищем закономерность

В большинстве заданий 16 таблица или мемоизированная рекурсия досчитывают до N за доли секунды, и на этом решение заканчивается. Но иногда выражение в вопросе устроено так, что проще вывести формулу, чем считать миллионы шагов, — особенно если один из аргументов участвует в громоздком произведении или если сама функция растёт быстрее, чем можно напечатать. Метод один: посчитайте программой первые 10–15 значений, выпишите их в столбик и поищите закономерность.

Возьмём условие с F(26) из блока формулировок: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно; F(n) = 2 × F(n − 2), если n > 1 и нечётно. Напечатаем первые значения на нечётных n:

from functools import lru_cache

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

for n in range(1, 16, 2):
    print(n, F(n))

# 1 1
# 3 2
# 5 4
# 7 8
# 9 16
# 11 32
# 13 64
# 15 128

Закономерность видна сразу: на нечётных n значение удваивается каждый раз, то есть $F(2k+1) = 2^{k}$ . Отсюда $F(25) = F(2 \cdot 12 + 1) = 2^{12} = 4096$ без единого шага рекурсии — а дальше по определению $F(26) = 26 + F(25) = 26 + 4096 = 4122$ . Такой вывод пригодился бы, если бы в вопросе стояло не F(26), а, скажем, F(200000): прямая рекурсия с мемоизацией всё ещё справилась бы, но формула считается мгновенно и подходит для любого N.

Второй типичный случай закономерности — телескопическое сокращение в выражениях вида F(N) / F(N − k) или F(N) − F(N − k) для функций-факториалов (F(n) = n × F(n − 1)). Раскрывать такую дробь до конца не нужно — распишите первые 2–3 шага руками:

\frac{F(446)}{F(443)} = \frac{446 \cdot 445 \cdot 444 \cdot F(443)}{F(443)} = 446 \cdot 445 \cdot 444

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

Три ловушки при переносе условия в код

1. Перепутанный порядок веток условия

Если в условии сначала стоит общее правило, а потом уточнение для частного случая, в коде более узкая проверка должна идти раньше общей — иначе она никогда не сработает. Например, база «F(n) = 1 при n <= 2» обязана проверяться до веток «если n чётно» / «если n нечётно», иначе при n = 2 сработает ветка для чётных чисел вместо базы, и вся цепочка вычислений пойдёт по неверному правилу.

2. Целочисленное деление // вместо обычного /

Оператор / в Python всегда возвращает дробное число (float), даже если результат целый: 10 / 2 — это 5.0, а не 5. Для больших значений функции float ещё и теряет точность в младших разрядах — целое число из 10 цифр округлится. Всегда используйте //, если по смыслу задачи ответ обязан быть целым (а в задании 16 он обязан быть целым всегда), и печатайте результат как int, а не как число с плавающей точкой.

3. Аргумент F уходит ниже базы рекурсии

Если условие переносится в код небрежно, легко получить вызов вроде F(0) или F(−1) там, где определение задаёт базу только для n = 1: функция либо упадёт с ошибкой при слишком глубокой рекурсии без явного возврата, либо — что хуже — тихо вернёт неверное число, если случайно совпало с одной из веток. Перед тем как запускать код, явно проверьте на бумаге: до какого именно значения дойдёт цепочка вызовов при уменьшении на 1 или на 2, и есть ли база ровно для этого значения.

Все три ошибки не проявляются на маленьких n — функция может годами «работать» на F(1)…F(5), пока вы не подставите настоящее большое N из условия. Поэтому шаблон кода нужно сверять с определением построчно, а не проверять на глаз.

Алгоритм решения задания 16

Выпишите базу (базы) и ветки перехода отдельно. Сколько баз, для каких n; сколько веток перехода, по какому признаку они различаются (чётность, диапазон, остаток от деления) и на сколько уменьшается аргумент в каждой.
Определите, что именно спрашивает вопрос. Само F(N), разность, частное или сумма нескольких значений функции — отвечать нужно на всё выражение целиком.
Переведите определение в код Python один в один — по одной проверке if на каждую ветку условия, в том же порядке: сначала база (или базы), затем переходы от более узкого условия к более широкому.
Добавьте sys.setrecursionlimit(100000) и @lru_cache(maxsize=None) — по умолчанию, для любой рекурсивной реализации, ещё до первого запуска.
Прогоните код на маленьких n, для которых можно посчитать вручную (обычно первые 3–5 значений после базы), и сверьте — это дешёвая проверка, что ветки не перепутаны местами.
Оцените размер N. Для N в пределах нескольких миллионов таблица или мемоизированная рекурсия досчитают за разумное время. Если N в вопросе на порядки больше — напечатайте первые 10–15 значений и поищите закономерность (арифметическую или геометрическую прогрессию, телескопическое сокращение).
Проверьте тип деления и запишите число. Используйте //, если ответ обязан быть целым, и напечатайте результат как целое число без пробелов и дополнительных символов.

Доведите шаблон кода до автоматизма

Прорешайте 10–15 функций подряд — и перевод условия в рекурсию на Python займёт меньше двух минут. Задания 16 ЕГЭ по информатике из банка ФИПИ с проверкой ответа — на Repet.ai.

Открыть тренажёр

Примеры с разбором

Пример 1. Факториал и телескопическая разность

Условие (реальное задание из открытого банка ФИПИ):

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n > 1. Чему равно значение выражения (F(2024) − F(2023)) / F(2022)?

Решение:

Одна база (n = 1) и один переход, который умножает предыдущее значение на n — это в точности определение факториала: $F(n) = n!$ . Раскрывать факториал из тысяч цифр не нужно — распишите числитель через F(2022), применяя переход трижды:

F(2023) = 2023 \cdot F(2022), \qquad F(2024) = 2024 \cdot F(2023) = 2024 \cdot 2023 \cdot F(2022)

Тогда разность в числителе выражения

F(2024) - F(2023) = 2023 \cdot F(2022) \cdot (2024 - 1) = 2023^{2} \cdot F(2022)

и после деления на F(2022) (которое встречается в обеих частях и просто сокращается) остаётся:

\frac{F(2024) - F(2023)}{F(2022)} = 2023^{2} = 4\,092\,529

Проверка кодом — с мемоизацией и поднятым лимитом рекурсии, как описано выше, только через целочисленное деление:

import sys
from functools import lru_cache

sys.setrecursionlimit(100000)

@lru_cache(maxsize=None)
def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)

print((F(2024) - F(2023)) // F(2022))

Ответ: 4092529. Быстрая проверка здравым смыслом: $2023^2$ действительно равно 4 092 529 (2023 × 2023), а по величине ответ на четыре порядка меньше самих F(2022)–F(2024) — это ожидаемо, ведь в выражении сократились все общие множители, кроме нужных трёх.

Пример 2. Две ветки по чётности и геометрическая прогрессия

Условие (реальное задание из открытого банка ФИПИ):

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n — чётно; F(n) = 2 × F(n − 2), если n > 1 и при этом n — нечётно. Чему равно значение функции F(26)?

Решение:

База — F(1) = 1. Две ветки перехода: для чётных n аргумент уменьшается на 1, для нечётных n > 1 — сразу на 2. Число 26 чётно, поэтому первый шаг однозначен:

F(26) = 26 + F(25)

Осталось найти F(25). Число 25 нечётно, и правило F(n) = 2 × F(n − 2) уменьшает аргумент на 2, оставляя его нечётным — значит, вся цепочка от 25 идёт только по нечётным числам и нигде не заходит в чётную ветку:

F(25) = 2F(23) = 4F(21) = \dots = 2^{12} \cdot F(1)

От 25 до 1 — ровно 12 шагов по 2, поэтому $F(25) = 2^{12} = 4096$ и $F(26) = 26 + 4096 = 4122$ . Проверка кодом, который переписывает условие один в один:

from functools import lru_cache

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

print(F(26))

Ответ: 4122. Проверка здравым смыслом: значение растёт по нечётным n как чистая степень двойки (1, 2, 4, 8, …, 4096), а единственное сложение на всю цепочку — самое последнее, «+26» — вносит уже сравнительно небольшую добавку к 4096. Число 4122 — это 4096 плюс 26, ровно как в определении.

Пример 3. Смешанные ветки с суммой по всем предыдущим значениям

Условие (реальное задание из открытого банка ФИПИ):

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1 при n < 3; F(n) = F(n − 1) + F(n − 2), если n > 2 и при этом n нечётно; F(n) = сумма F(i) по i от 1 до n − 1, если n > 2 и при этом n чётно. Чему равно значение функции F(24)?

Решение:

База здесь одна строка, но покрывает сразу три значения: «n < 3» — это n = 0, n = 1 и n = 2, и для всех них F(n) = 1. Дальше две ветки: для нечётных n > 2 — как у чисел Фибоначчи, для чётных n > 2 — сумма всех предыдущих значений, начиная с F(1) (F(0) в сумму не входит, потому что она начинается с i = 1). Такую функцию удобнее всего считать таблицей — переход по одной строке нельзя выполнить в общем виде без хранения всех значений сразу:

F = [0] * 25
F[0] = F[1] = F[2] = 1
for n in range(3, 25):
    if n % 2 == 1:
        F[n] = F[n - 1] + F[n - 2]
    else:
        F[n] = sum(F[1:n])

print(F[24])

Первые значения по шагам:

n	F(n)	n	F(n)
1	1	6	14
2	1	7	20
3	2	8	48
4	4	…	…
5	6	24	887040

Ответ: 887040. Проверка здравым смыслом: значение на чётных n почти удваивается от шага к шагу (14 → 48 → 164 → … → 887040), потому что каждая чётная сумма включает в себя предыдущую чётную сумму почти целиком плюс всё, что накопилось между ними, — устойчивый быстрый рост без скачков и провалов подтверждает, что ни одна ветка не была применена по ошибке.

Типичные ошибки и ловушки

RecursionError на большом N

Функция написана верно, но при F(2024) или F(5000) программа падает с ошибкой глубины рекурсии. Причина — лимит Python по умолчанию (около 1000 вложенных вызовов), а не ошибка в логике. Решение — sys.setrecursionlimit(100000) в начале файла, до первого вызова функции.

Код «висит» без ошибок и без ответа

Типичный признак функции с двумя рекурсивными вызовами (F(n − 1) и F(n − 2) одновременно) без мемоизации: дерево вызовов растёт экспоненциально, и на N в несколько тысяч программа не досчитает за разумное время, даже без переполнения глубины. Добавьте @lru_cache(maxsize=None) над функцией — и то же вычисление займёт доли секунды.

Перепутанный порядок веток условия

Более узкое условие (обычно база) проверяется в коде после более широкого — и никогда не срабатывает. Например, если проверку «n <= 2 → база» в коде поставить третьей строкой после проверок на чётность, для n = 2 сработает ветка «чётное», а не база, и все вычисления пойдут по неверному правилу с самого начала.

Обычное деление вместо целочисленного

Оператор / в Python возвращает float, и при больших значениях это ещё и потеря точности в младших разрядах — «красивое» целое число может превратиться в дробь с ошибкой округления или в число с «e» в записи. Для задания 16 ответ всегда целый — используйте // и печатайте результат как int.

Ответили на F(N), а спрашивали про выражение

Вопрос часто звучит как «чему равно (F(2024) − F(2023)) / F(2022)», а не «чему равно F(2024)». Посчитать только F(N) и записать его в бланк — частая невнимательность: перечитайте вопрос ещё раз перед тем, как печатать ответ, и убедитесь, что вычислили именно то выражение, которое спросили.

Печать огромного промежуточного числа

Если функция растёт как факториал, F(2024) — это число из тысяч цифр, и современный Python откажется напечатать его целиком без отдельной настройки интерпретатора. Печатайте не промежуточные значения функции, а итоговое выражение из вопроса — оно почти всегда получается на порядки меньше.

Автор кода угадывает поведение функции «по аналогии»

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

Как задание 16 связано с остальным экзаменом

Всего в работе 27 заданий, все с кратким ответом, максимальный первичный балл — 29, на всю работу отводится 235 минут. Задание 16 занимает в этой структуре особое место:

оно входит в раздел «Алгоритмы и программирование» вместе с заданиями 5, 6, 12, 17, 23, 24, 25 и 26 — по числу заданий это второй по величине раздел кодификатора после «Теоретических основ информатики»;
делит редкую особенность формы работы с заданием 25: на обоих требуется среда программирования, но входного файла нет — вся нужная для решения информация дана прямо в условии;
логически продолжает задание 12 (тоже формальное исполнение алгоритма, тот же принцип «переписать условие в код построчно»), но там объект — строка и команды исполнителя, а в задании 16 — числовая функция и её рекуррентное определение;
делит с заданием 17 требование к среде программирования; те же приёмы работы с Python — мемоизация и аккуратный перенос условия в код — пригодятся и на задании 23, хотя формально спец. ПО там не требуется;
приём «посчитать первые значения и найти закономерность» — общий с заданиями на числовые последовательности и с задачами олимпиадного уровня по программированию; отработав его на задании 16, вы получаете универсальный инструмент, а не разовый трюк.

Задание 12 — исполнитель Редактор Задание 17 — обработка числовой последовательности Задание 25 — тоже среда программирования без файла Все задания ЕГЭ по информатике

План подготовки на 2 недели

Неделя 1 — читаем условие и пишем код без ошибок

День 1–2: возьмите 5–6 функций из открытого банка и, не решая их, просто выпишите отдельно базу (базы) и ветки перехода — тренируйте именно чтение условия. День 3–5: переводите каждую функцию в Python построчно, добавляя sys.setrecursionlimit(100000) и @lru_cache(maxsize=None) по умолчанию, и сверяйте первые 5 значений с ручным счётом. День 6–7: намеренно решите несколько задач без мемоизации на умеренном N (30–35), чтобы своими глазами увидеть замедление, а потом добавьте lru_cache и почувствуйте разницу.

Неделя 2 — закономерности и скорость

День 1–3: для функций с быстрым ростом (факториалы, степени двойки) потренируйтесь выводить закономерность руками — печатайте первые 10–15 значений и ищите формулу, затем проверяйте её на ещё двух-трёх значениях, которые не использовали при выводе. День 4–5: решайте задания на выражения из нескольких значений функции (разности, частные), чтобы не терять внимание на переходе от «F(N) найдено» к «выражение из вопроса найдено». День 6–7: работайте на время — 5 минут на задание, включая запуск кода, — и проверьте себя в тренажёре на заданиях из банка ФИПИ.

Проверьте себя на реальных заданиях

На Repet.ai собраны задания ЕГЭ по информатике из открытого банка ФИПИ. Решайте онлайн, проверяйте ответ мгновенно и разбирайте решение — бесплатно.

Перейти к практике

Частые вопросы

Часто задаваемые вопросы

Умение вычислять рекуррентные выражения. В условии дана функция F(n), заданная через базу (готовые значения при малых n) и переход (правило, которое выражает F(n) через значения при меньших аргументах). Нужно найти значение F(N) для конкретного большого N или выражение из нескольких значений функции. В кодификаторе это элемент содержания 3.7, требование 1.8, раздел «Алгоритмы и программирование».

1 первичный балл по принципу «всё или ничего»: ответ либо полностью совпадает с эталоном, либо задание оценивается в 0. Полубаллов нет. По обобщённому плану ФИПИ на задание 16 отводится примерно 5 минут. Уровень сложности — повышенный.

Нет. Задание 16 требует среду программирования (доступны C#, C++, Pascal, Java, Python), но входного файла к нему не прилагается — вся функция целиком описана в тексте условия. Такая же особенность у задания 25.

Построчно: каждая ветка условия становится проверкой if в том же порядке, в котором она записана — сначала база (или базы), затем переходы. Каждое обращение к F в правой части правила становится рекурсивным вызовом функции с тем же аргументом, что в условии (обычно n − 1 или n − 2). Ничего добавлять от себя не нужно — перенос должен быть дословным.

По умолчанию Python обрывает цепочку вызовов примерно после 1000 уровней вложенности и выдаёт RecursionError. Аргументы в задании 16 часто исчисляются тысячами, поэтому в начале программы нужно поднять лимит: import sys; sys.setrecursionlimit(100000).

Если переход обращается к функции сразу от двух предыдущих значений (например, F(n − 1) и F(n − 2) одновременно), без сохранения результатов дерево вызовов растёт экспоненциально и одни и те же значения пересчитываются заново тысячи раз. Декоратор @lru_cache(maxsize=None) над функцией запоминает уже посчитанные значения и превращает экспоненциальное время счёта в линейное.

Напечатать программой первые 10–15 значений функции и поискать закономерность — арифметическую или геометрическую прогрессию, телескопическое сокращение в дроби или разности. Найденную формулу подставляют напрямую, без единого шага рекурсии, и проверяют ещё на паре значений, не использованных при выводе.

Ответ — одно целое число, без пробелов, знаков равенства и других символов. Значения в этих заданиях быстро становятся многозначными — большое число само по себе не повод пересчитывать заново. Используйте целочисленное деление (//), а не обычное (/), если по смыслу задачи результат обязан быть целым.

Готовы взять балл повышенного уровня?

Задание 16 решается одним и тем же приёмом почти всегда: переписать условие в код построчно, поднять лимит рекурсии, добавить мемоизацию. Отработайте это на реальных функциях из открытого банка ФИПИ с мгновенной проверкой ответа — и рекурсия перестанет быть источником обидных ошибок.

Тренировать задание 16 Задание 25 — тоже без файла Все задания ЕГЭ по информатике