Как решать задание 16 ЕГЭ по информатике — рекурсивные функции
Разбор задания 16 ЕГЭ по информатике: рекурсивные функции, базовый случай, мемоизация, таблица значений. Пошаговые примеры на Python и типичные ошибки.
О чём задание
Задание 16 КЕГЭ — это рекурсивные функции. Тебе дают одну, две или три функции, которые вызывают сами себя (и друг друга), и просят посчитать значение F(N) для конкретного N или найти N с заданным свойством. Задание базового уровня, стоит 1 первичный балл. Всего в КЕГЭ 2026 — 27 заданий на 235 минут, 29 первичных баллов: задания 1-25 по 1 баллу, задания 26 и 27 по 2 балла. Подробности о структуре экзамена — в статье ЕГЭ по информатике 2026 — что изменилось.
Задание 16 традиционно считается одним из самых «дружелюбных» в экзамене: решается в 5-10 строк Python, никаких хитрых условий, формула дана явно. Но именно здесь теряют балл те, кто пытается считать руками и ошибается в арифметике на 2-3-м шаге.
Что такое рекурсивная функция
Рекурсивная функция — это функция, которая вызывает саму себя. Классический пример — факториал:
def fact(n):
if n == 0: # базовый случай
return 1
return n * fact(n - 1) # рекурсивный шаг
У любой корректной рекурсии есть две части:
- Базовый случай — условие, при котором функция возвращает результат без новых вызовов. Для
factэтоn == 0 → 1. Это точка остановки: если её не будет, функция провалится в бесконечную рекурсию и Python выдастRecursionError: maximum recursion depth exceeded - Рекурсивный шаг — выражение, которое сводит задачу к задаче меньшего размера. Для
factэтоn * fact(n-1): задача размераnсведена к задаче размераn-1
В задании 16 базовый случай всегда написан в условии. Твоя работа — аккуратно перенести формулы в Python и вызвать функцию.
Пример формулы из ЕГЭ
Типичная формулировка из демоверсии:
Алгоритм вычисления значения функции F(n) задан соотношениями:
F(n) = 1 при n < 1
F(n) = F(n-1) + F(n-2) + n при n ≥ 1
Чему равно F(6)?
Переносим в Python буквально:
def F(n):
if n < 1:
return 1
return F(n-1) + F(n-2) + n
print(F(6))
Запускаешь — получаешь ответ. Вся логика в трёх строках.
Типы вопросов в задании 16
За последние годы на ЕГЭ встречались четыре основных типа задач:
- Посчитать F(K) — дан N, нужно получить число. Самый простой вариант
- Найти сумму — например,
F(5) + F(6) + F(7) - Найти минимальное (или максимальное) N — «наименьшее N, при котором F(N) > 10000»
- Количество рекурсивных вызовов — сколько раз функция вызывает саму себя при вычислении F(N)
Иногда встречаются задачи на две взаимно рекурсивные функции F и G, где F вызывает G, а G вызывает F. Принцип тот же — переносим обе формулы в код и запускаем.
Три подхода к решению
Подход 1: таблица значений
Если вычисление идёт от малых к большим, удобно построить таблицу F[0], F[1], ..., F[N] в цикле:
N = 20
F = [0] * (N + 1)
for n in range(N + 1):
if n < 1:
F[n] = 1
else:
F[n] = F[n-1] + F[n-2] + n
print(F[6]) # ответ на F(6)
print(F) # вся таблица сразу
Плюсы: не упирается в лимит рекурсии, можно сразу увидеть как растут значения, удобно для поиска минимального N с условием.
Подход 2: прямая рекурсия
Просто переносим формулу. Подходит для небольших N (до 25-30), потому что при больших значениях функция начинает пересчитывать одни и те же F(k) тысячи раз и виснет.
def F(n):
if n < 1:
return 1
return F(n-1) + F(n-2) + n
print(F(6))
Подход 3: рекурсия + мемоизация
Главный трюк задания 16 для больших N. Сохраняем уже посчитанные значения в словаре, чтобы не считать их повторно:
def F(n, memo={}):
if n in memo:
return memo[n]
if n < 1:
return 1
res = F(n-1) + F(n-2) + n
memo[n] = res
return res
print(F(100))
В этом варианте F(100) считается мгновенно, потому что каждое F(k) вычисляется ровно один раз. Альтернатива — декоратор @lru_cache:
from functools import lru_cache
@lru_cache(maxsize=None)
def F(n):
if n < 1:
return 1
return F(n-1) + F(n-2) + n
Важная оговорка: если в задаче спрашивается количество вызовов, мемоизация запрещена — она исказит ответ.
Про setrecursionlimit
По умолчанию Python ограничивает глубину рекурсии 1000 вызовов. Для задания 16 это почти всегда хватает. Но если задача требует посчитать F(500), и ты получил RecursionError, добавь две строки:
import sys
sys.setrecursionlimit(10000)
Либо (и это обычно надёжнее) — перепиши через таблицу значений. Таблица не упирается в лимит стека вообще.
Пошаговый разбор примера 1
Условие. Функция F задана так:
- F(n) = 1 при n < 2
- F(n) = F(n-1) + F(n-2) + 2n при n ≥ 2
Найди F(8).
Шаг 1. Переносим формулу в Python буквально:
def F(n):
if n < 2:
return 1
return F(n-1) + F(n-2) + 2 * n
Шаг 2. Добавляем вызов:
print(F(8))
Шаг 3. Проверяем себя — строим таблицу вручную для малых значений:
| n | F(n) | Как посчитан |
|---|---|---|
| 0 | 1 | базовый случай |
| 1 | 1 | базовый случай |
| 2 | F(1) + F(0) + 4 = 1 + 1 + 4 = 6 | |
| 3 | F(2) + F(1) + 6 = 6 + 1 + 6 = 13 | |
| 4 | F(3) + F(2) + 8 = 13 + 6 + 8 = 27 | |
| 5 | F(4) + F(3) + 10 = 27 + 13 + 10 = 50 | |
| 6 | F(5) + F(4) + 12 = 50 + 27 + 12 = 89 | |
| 7 | F(6) + F(5) + 14 = 89 + 50 + 14 = 153 | |
| 8 | F(7) + F(6) + 16 = 153 + 89 + 16 = 258 |
Ответ: 258. Запуск Python даёт то же число — значит, не ошибся.
Пошаговый разбор примера 2
Условие. Даны две функции:
- F(n) = 1 при n ≤ 2
- F(n) = F(n-1) + G(n-2) при n > 2
- G(n) = 1 при n ≤ 2
- G(n) = G(n-1) + F(n-1) при n > 2
Найди значение F(10) + G(10).
Шаг 1. Пишем обе функции с мемоизацией (здесь взаимная рекурсия, без кэша будет медленно при N > 20):
from functools import lru_cache
@lru_cache(maxsize=None)
def F(n):
if n <= 2:
return 1
return F(n-1) + G(n-2)
@lru_cache(maxsize=None)
def G(n):
if n <= 2:
return 1
return G(n-1) + F(n-1)
print(F(10) + G(10))
Шаг 2. Строим таблицу для самопроверки:
| n | F(n) | G(n) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | F(2)+G(1)=2 | G(2)+F(2)=2 |
| 4 | F(3)+G(2)=3 | G(3)+F(3)=4 |
| 5 | F(4)+G(3)=5 | G(4)+F(4)=7 |
| 6 | F(5)+G(4)=9 | G(5)+F(5)=12 |
| 7 | F(6)+G(5)=16 | G(6)+F(6)=21 |
| 8 | F(7)+G(6)=28 | G(7)+F(7)=37 |
| 9 | F(8)+G(7)=49 | G(8)+F(8)=65 |
| 10 | F(9)+G(8)=86 | G(9)+F(9)=114 |
F(10) + G(10) = 86 + 114 = 200. Совпадает с выводом программы.
Обрати внимание: таблица помогает ловить ошибки переноса формулы. Если в программе получилось другое число, а в таблице ты уверен — значит, где-то в коде опечатка (перепутал F и G, n и n-1, и т.п.).
Задача на количество вызовов
Условие. Сколько раз будет вызвана функция F при вычислении F(7), если:
- F(n) = 1 при n < 2
- F(n) = F(n-1) + F(n-2) при n ≥ 2
Решение. Добавляем глобальный счётчик без мемоизации — вопрос именно про количество «физических» вызовов:
cnt = 0
def F(n):
global cnt
cnt += 1
if n < 2:
return 1
return F(n-1) + F(n-2)
F(7)
print(cnt) # 41
Важно: если накинуть @lru_cache, счётчик покажет меньше вызовов — это будет другая задача. Формулировка «сколько раз будет вызвана функция» почти всегда подразумевает наивную реализацию.
Задача на поиск N по порогу
Условие. Найди минимальное N, при котором F(N) > 1000, если F(n) = F(n-1) + F(n-2) + n, F(n) = 1 при n < 2.
Решение. Строим таблицу в цикле и останавливаемся как только значение превысит порог:
F = [1, 1]
n = 2
while F[-1] <= 1000:
F.append(F[n-1] + F[n-2] + n)
n += 1
print(n - 1, F[-1])
Вывод: 12 1188 — значит, минимальное N равно 12. Этот паттерн (построить таблицу и дождаться условия) работает для 90% задач на «найди минимальное N».
Типичные ошибки
Ошибка 1: забыл базовый случай. Самая частая. Если в программе нет if n < ..., Python уйдёт в бесконечную рекурсию и крашнется. Всегда пиши базовый случай первой строкой функции.
Ошибка 2: перепутал границу. В условии при n < 1 — это значит F(0) = 1, а F(1) считается по формуле. А при n ≤ 1 означает, что и F(0), и F(1) равны 1. Читай неравенство буквально: < и ≤ — это разные базовые случаи.
Ошибка 3: считает вручную с ошибкой. Если посчитал F(6) руками и не проверил Python — почти гарантированно где-то ошибся в одной из 6 строк таблицы. Лучше сразу писать программу.
Ошибка 4: забыл умножить на коэффициент. В формуле F(n-1) + F(n-2) + 2n коэффициент 2 пропускают каждый третий раз. Внимательно перечитывай формулу.
Ошибка 5: мемоизация там, где её нельзя. Если спрашивают количество вызовов — убери @lru_cache и словари. Иначе ответ будет неправильный.
Подборка других типичных промахов — в статье Топ-5 ошибок на ЕГЭ по информатике.
Тайминг на экзамене
Рекомендуемое время — 5-8 минут:
- 1-2 минуты — прочитать формулу и перенести её в Python
- 1 минута — запустить и получить ответ
- 1-2 минуты — построить таблицу для самопроверки (если числа маленькие)
- 1-2 минуты — записать ответ в бланк
Если ты решаешь задание 16 дольше 10 минут — ты делаешь что-то лишнее. Чаще всего это попытка посчитать всё руками. Не трать время — пиши функцию и вызывай.
Как тренироваться
- Начни с одной функции. 10-15 задач с формулами вида
F(n) = F(n-1) + c*n. Цель — научиться за 30 секунд переносить формулу в Python - Перейди к двум функциям. F и G, которые вызывают друг друга. Обязательно с мемоизацией
- Потрогай счётчик вызовов. Задачи, где нужно посчитать количество срабатываний функции. Научись считать без кэша
- Порешай задачи на пороги. «Минимальное N, при котором F(N) > X» — стандартный подтип
Для поддержки Python-навыков посмотри подборку полезных идиом для ЕГЭ — цикл по таблице, @lru_cache, аккуратная мемоизация через словарь. Если готовишься с нуля — начни с пошагового плана. А если есть сомнения, хватит ли Python на все 27 заданий — в статье Python или C++ для ЕГЭ сравнение языков для КЕГЭ.
В TuteMe есть целая ветка задач на рекурсивные функции: одиночные, взаимно рекурсивные, с мемоизацией и без. После каждой попытки показывается таблица значений и дерево вызовов — удобно ловить ошибки.