Задание 16 ЕГЭ по информатике: рекурсия
В шестнадцатом задании ЕГЭ по информатике функция задана рекуррентно: F(n) выражается через F(n − 1) или другие значения. Нужно вычислить F для конкретного n. Python справляется за секунду, но при больших n нужна хитрость: либо кэш и запас глубины рекурсии, либо упрощение выражения вручную.
Для 10–11 классов. Нумерация по проекту демоверсии ФИПИ на 2027 год.
Разбор задач
Сумма
F(1) = 1, F(n) = n + F(n − 1) при n > 1. Найдите F(100).
F(n) это сумма чисел от 1 до n.
100·101/2 = 5050.
Ответ: 5050
Двухшаговая
F(n) = n при n < 3, F(n) = F(n − 1) + F(n − 2) при n ≥ 3. Найдите F(10).
F(1) = 1, F(2) = 2, дальше 3, 5, 8, 13, 21, 34, 55, 89.
F(10) = 89.
Ответ: 89
Огромные значения
F(1) = 1, F(n) = n·F(n − 1). Найдите F(2024)/F(2022).
F(n) это n!, а 2024!/2022! = 2024·2023.
2024·2023 = 4 094 552.
Ответ: 4094552
Код на Python
from functools import lru_cache import sys sys.setrecursionlimit(10000) @lru_cache(None) def F(n): if n < 3: return n return F(n - 1) + F(n - 2) print(F(10))
Без lru_cache двухшаговая рекурсия считается экспоненциально долго уже при n около 40. setrecursionlimit нужен, если n больше тысячи. Ещё надёжнее считать снизу вверх циклом, сохраняя значения в списке.
Проверь себя
- F(0) = 0, F(n) = F(n − 1) + 2 при n > 0. F(50)? Ответ: 100.
- F(1) = 2, F(n) = 2·F(n − 1). F(10)? Ответ: 1024.
Где теряют балл
- Не тот базовый случай. Внимательно перенесите условия «при n < 3», «при n = 1».
- Переполнение глубины. При большом n Python выдаёт RecursionError. Увеличьте лимит или считайте циклом.
Как тренироваться
Рекурсия используется и в заданиях 19–21 на теорию игр: задание 19. Все номера экзамена в статье ЕГЭ по информатике по номерам.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Обязательно ли писать рекурсию?
Нет, можно считать циклом с массивом значений. Часто это даже быстрее.
Сколько баллов?
Один первичный балл.