ЕГЭ по информатике: Задание 16 — рекурсия с большими аргументами

Задание 16 ЕГЭ по информатике — вычисление рекуррентных выражений. В 2026 году, как и в предыдущие годы, функции в нём задаются так, что нужное значение лежит далеко от базового случая: аргумент исчисляется тысячами. Прямой рекурсивный вызов в Python завершается ошибкой переполнения стека, а наивная ветвящаяся рекурсия работает слишком долго. Поэтому задание проверяет два элемента кодификатора: 3.7 (рекурсия и стек вызовов) и 3.16 (динамическое программирование — вычисление рекурсивных функций с сохранением промежуточных результатов).

Материал разбирает оба пути к ответу. Аналитический: для рекурренты вида F(n) = F(n − 1) + d значение выражается формулой, для F(n) = n · F(n − 1) выражения с большими аргументами упрощаются вынесением общего множителя, разность F(n) − F(n − 1) часто следует прямо из определения, а для пары функций F и G достаточно понять, сколько шагов спуска нужно, чтобы дойти до базовой зоны. Программный: sys.setrecursionlimit увеличивает допустимую глубину, lru_cache избавляет от повторных вычислений, «прогрев» кэша и заполнение таблицы значений в цикле снизу вверх позволяют обойтись без глубокой рекурсии вовсе.

Вопросы проверяют и понимание механизма: почему возникает RecursionError, чем отличаются глубина рекурсии и число вызовов, сколько раз вызывается функция с кэшем и без него, что выведет короткая программа с таблицей значений. Небольшие задачи с ветвлением по чётности тренируют аккуратную ручную трассировку. Все ответы вычислены программой.

Письменная работа предлагает вывести значение при большом n с обоснованием, записать программу, которая не упирается в предел глубины рекурсии, и объяснить разницу между setrecursionlimit и lru_cache. На устном экзамене нужно найти значение функции для большого аргумента и объяснить выбранный способ. Карточки собирают приёмы и понятия задания 16.

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

  • Находить значения рекуррентных функций при больших аргументах аналитически
  • Упрощать выражения с факториальными и взаимно рекурсивными функциями
  • Объяснять причину RecursionError и способы её избежать
  • Применять lru_cache и вычисление снизу вверх
  • Подсчитывать число рекурсивных вызовов с кэшем и без него

Кодификатор ЕГЭ 2026 по информатике: 3.7 — рекурсия, использование стека для организации рекурсивных вызовов; 3.16 — динамическое программирование, вычисление рекурсивных функций. Спецификация 2026: задание 16, повышенный уровень, около 5 минут, среда программирования.

Пример вопроса

Что произойдёт при запуске программы с настройками Python по умолчанию? ```python def F(n): if n == 0: return 0 return F(n - 1) + 1 print(F(5000)) ```

Показать ответ

Программа завершится с ошибкой RecursionError: глубина рекурсии превысит установленный по умолчанию предел (около 1000 вызовов)

Каждый вызов F(n) ждёт результата F(n − 1), поэтому одновременно в стеке оказывается около 5000 вызовов. Стандартный предел глубины рекурсии в CPython — 1000, поэтому возникает RecursionError. Исправить можно, увеличив предел (sys.setrecursionlimit) или переписав вычисление циклом.

← Информатика

↑ ЕГЭ