16
1 балл демоверсия ЕГЭ-2026
Рекурсивные функции: чтение и счёт по формулам
Задание 16 · Билет 1 · ЕГЭ по информатике
Билет 1 — демоверсия ЕГЭ-2026; остальные билеты — задания в формате экзамена (открытый сборник или тренировочные по образцу). Это тренировочные материалы, а не официальные КИМ. Ответы пересчитаны и сверены.
Условие
Алгоритм вычисления функций и , где — целое число, задан соотношениями:
, если
, если
Вопрос. Чему равно значение выражения ?
Разбор задачи
Задание 16 ЕГЭ по информатике — это рекурсия: функция задана через саму себя, и нужно посчитать её значение при большом аргументе.
Функция задана двумя частями: базой (когда вызова самой себя нет и значение считается сразу) и рекурсивным шагом (вызов себя с меньшим аргументом). Небольшой аргумент раскрывают вручную, чтобы увидеть закономерность, а значение большого считают по числу шагов до базы или короткой программой.
Что важно знать
- Задание базового уровня — оценивается в 1 балл
- У рекурсии всегда есть база — иначе она не остановилась бы
- Каждый шаг приближает аргумент к базе
- Большой аргумент не раскрывают вручную: считают число шагов до базы
План решения
- Выпишите отдельно базу и рекурсивный шаг
- Подставьте нужный аргумент и определите, какая строчка подходит
- Проследите, как аргумент уменьшается до базы
- Посчитайте число шагов до базы и значение на базе
- Соберите ответ обратным ходом — или посчитайте таблицу короткой программой
- Проверьте ответ на маленьком аргументе
Не знаешь, как решать?
Открыть тренажёрПотренируйся на рекурсии: найди базу и рекурсивный шаг и посчитай значение функции — от разминки до формата экзамена.
Решение
Теория с нуля: что нужно знать
1. Что такое рекурсия (на примере факториала)
Рекурсия — это когда функция решает задачу, вызывая саму себя с более простым аргументом, и так повторяется, пока задача не станет настолько простой, что решается сразу. Такой «простой случай» называют базой.
Возьмём самый известный пример — факториал: (произведение чисел от 1 до ). Его удобно задать рекурсией: — база (уменьшать дальше некуда)
, если — рекурсивный шаг
Смотрим, как это работает на числе . Сначала идём «вглубь», каждый раз уменьшая аргумент на 1: ← база: дальше не идём
Итог: . Никакой магии — функция просто зовёт саму себя с меньшим числом, пока не дойдёт до базы, а потом возвращается «вверх», подставляя результаты. Ровно так же «раскрываются» функции из нашей задачи.
Перед нами тоже задача на рекурсию: функции определены через самих себя. Слово «рекурсия» в условии не написано — его нужно увидеть: если в определении функции есть вызов той же функции, это рекурсия. — вызывает ; — вызывает (и через него связана с той же цепочкой).2. Почему для G две строчки? Это два разных вызова?
Нет — это одна функция , заданная кусочно (как if/else в программировании). Для конкретного аргумента берётся ровно одна строчка — та, чьё условие подходит:
• если → первая строчка: (сразу ответ);
• если → вторая строчка: (рекурсивный шаг).
делает один вызов . При его вычислении снова смотрим на аргумент и выбираем подходящую строчку; из второй появляется новый вызов с меньшим аргументом — и так до базы. Пример: .
• если → первая строчка: (сразу ответ);
• если → вторая строчка: (рекурсивный шаг).
делает один вызов . При его вычислении снова смотрим на аргумент и выбираем подходящую строчку; из второй появляется новый вызов с меньшим аргументом — и так до базы. Пример: .
3. Полный разворот вызовов на маленьком числе
Посмотрим наглядно, как рекурсия «раскрывается» вызов за вызовом. Возьмём :
Теперь посмотрим, как использует , на примере :
← 12 ≥ 10, вторая строчка
← 10 ≥ 10, вторая строчка
← 8 < 10, первая строчка: база
возврат:
возврат:
Каждый вызов выбирает строчку по своему аргументу: 12 → 10 → 8 → база; возвращаемся «назад», добавляя +1 на каждом шаге.Теперь посмотрим, как использует , на примере :
← 9 < 10, база
вызывает ровно один раз, а уже сама «раскрывается» по своим правилам.
4. База и рекурсивный шаг
У любой рекурсии две части.
База (базовый случай) — случай, когда функция НЕ вызывает себя, а сразу возвращает значение: здесь это при . Без базы рекурсия не остановилась бы никогда.
Рекурсивный шаг — случай, когда функция вызывает себя с меньшим аргументом: . Каждый вызов «расходует» аргумент, пока тот не попадёт в базу.
База (базовый случай) — случай, когда функция НЕ вызывает себя, а сразу возвращает значение: здесь это при . Без базы рекурсия не остановилась бы никогда.
Рекурсивный шаг — случай, когда функция вызывает себя с меньшим аргументом: . Каждый вызов «расходует» аргумент, пока тот не попадёт в базу.
5. Как посчитать значение большой рекурсии
Вручную выполнять 15548 вызовов нельзя. Но каждый шаг уменьшает аргумент на 2, поэтому путь к базе детерминирован: из любого большого числа мы «спускаемся» к базе строго определённым маршрутом. Остаётся посчитать число шагов до базы и прибавить по за каждый шаг.
Шаг равен , а вычитание 2 не меняет чётность. Поэтому спуск из чётного аргумента закончится на чётной границе, из нечётного — на нечётной. Смотрим на базу:
• из нечётного числа придём к 9: ;
• из чётного числа придём к 10, но — это ещё не база! (один лишний шаг).
Проверка на чётность нужна не вместо правила «», а чтобы понять, к какой границе базы приведёт цепочка шагов .
Шаг равен , а вычитание 2 не меняет чётность. Поэтому спуск из чётного аргумента закончится на чётной границе, из нечётного — на нечётной. Смотрим на базу:
• из нечётного числа придём к 9: ;
• из чётного числа придём к 10, но — это ещё не база! (один лишний шаг).
Проверка на чётность нужна не вместо правила «», а чтобы понять, к какой границе базы приведёт цепочка шагов .
Решение
открыто шагов: 4 из 41 Шаг 1
Подход. Это рекурсия: вызывает , а вызывает саму себя. Ищем базу (случай без вызова себя: ) и рекурсивный шаг (). Задача сводится к одному вызову : спускаемся по шагу до базы и считаем число шагов.
2 Шаг 2
Нужно . Находим .
3 Шаг 3
— нечётное, значит по пути дойдём до базы . Число шагов: .
4 Шаг 4
. Тогда .
Правильный ответ этого билета: 15588
Проверка: . Совпадает с эталоном демоверсии.
Проверка
Типовые ошибки и проверка
- Путают аргумент: считают , а не .
- Неверная база: и — их нельзя путать ( — потому что и база ).
- Ошибаются на единицу в числе шагов — проверяйте число шагов на маленьких числах.
- Забывают умножить на 2 и прибавить 8 в формуле .
- Проверка: подставьте небольшой аргумент и прогоните вручную по определениям, сверьте с формулой.
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки — только условие и поле ответа, без подсказок.
Практикум Все задания Режим проверки — скоро
Частые вопросы
Что проверяет задание 16 ЕГЭ по информатике?
Умение читать рекурсивно заданную функцию: находить базу и рекурсивный шаг и вычислять значение функции при заданном аргументе.
Что такое база рекурсии?
Это случай, когда функция не вызывает себя, а сразу возвращает значение (например, при ). Без базы рекурсия не остановилась бы.
Почему нельзя просто подставить большое число?
Функция вызывает себя с меньшим аргументом, поэтому значение «собирается» от базы наверх. Для этого считают число шагов до базы, а не раскрывают все вызовы вручную.
Как не ошибиться на единицу?
Проверяйте формулу числа шагов на маленьких аргументах: подставьте небольшое и прогоните цепочку вызовов вручную.
Можно ли потренировать задание 16?
Да. Практикум собирает случайные рекурсивные функции: нужно вычислить значение, посчитав шаги до базы. Есть уровни, проверка ответа и разбор по шагам.