В этой статье рассмотрим рекуррентный способ решения задания № 16 из ЕГЭ по информатике.
Термины, которые будем использовать: рекурсия, кэш, кэширование, предел рекурсии, точка выхода (базовый случай), шаг рекурсии.[i]
Что такое рекурсия
Точка выхода (базовый случай) — момент, когда функция перестаёт вызывать себя и возвращает конкретный ответ.
Шаг рекурсии (рекурсивный вызов) — вызов функции с изменёнными, упрощёнными данными. Аналогия: «Сколько раз моргнуть?». Если 0 раз — стоп; если больше — моргни один раз и повтори с числом на 1 меньше.
Предел рекурсии — количество вызовов одной рекурсии. По умолчанию в Python предельная глубина рекурсии равна 1000. Это значит, что, если функция будет вызывать саму себя больше 1000 раз подряд, интерпретатор остановит выполнение и выдаст ошибку RecursionError: maximum recursion depth exceeded.[i]
Изменение предела рекурсии
Предел рекурсии можно изменить на любое другое число с помощью библиотеки sys и метода setrecursionlimit(), в качестве аргумента которому передаётся новое значение предела (обязательно целое, int).
import sys
sys.setrecursionlimit(3000)
def hello():
print(«Привет»)
hello() # вызывает саму себя
Теперь функция будет вызывать саму себя 3000 раз вместо 1000, пока не появится ошибка RecursionError: maximum recursion depth exceeded и программа завершится. [i]
Кэширование
Чаще всего, чтобы вычислить очередное значение функции, нужно знать её значение от предыдущего аргумента. По умолчанию рекурсия каждый раз считает всё заново — неважно, встретилось значение впервые или в десятый раз. Но работу рекурсии можно ускорить, подключив кэширование.
@lru_cache — это декоратор, который автоматически кэширует (сохраняет) результаты вызова функции для тех аргументов, с которыми она уже вызывалась. Если функция вызывается с теми же аргументами повторно, она не пересчитывает результат, а берёт готовый из кэша.
LRU расшифровывается как Least Recently Used («давно не использовавшийся»). Кэш хранит ограниченное количество результатов (по умолчанию 128) и при переполнении удаляет самые «старые» (реже всего использовавшиеся) записи.
Декоратор @lru_cache() нужно размещать непосредственно перед той функцией, к рекурсии которой он должен быть применён. Если передать ему параметр None (то есть @lru_cache(None)), кэш будет хранить все вычисленные значения без ограничения по объёму.[i]
Заключение
Задание № 16 удобно решать рекуррентно: достаточно перенести формулы из условия в функцию, разветвив их по базовому случаю и шагу рекурсии, а затем подставить нужные значения. Чтобы программа не упёрлась в предел рекурсии и не считала одно и то же по многу раз, значения заранее вычисляют снизу вверх — через кэш @lru_cache(None) или через список.
Разбор задач из ЕГЭ 2025 года
Задание 1 (ЕГЭ 2025, ДВ)
Алгоритм вычисления значения функции где n — натуральное число, задан следующими соотношениями:
f(n) = n, если n < 10, f(n) = n2+f(n-9), если n ≥ 10. Чему равно значение выражения f(5101) − f(5074)?[i]
Для рекуррентного решения просто переписываем нужный возврат значения из условия в зависимости от ограничения на n.
Первый способ решения — через кэш
from functools import *
@lru_cache(None)
def f(n):
if n < 10:
return n
return n**2 + f(n — 9)
# так как мы импортировали кэш, то для ускорения вычислений всех значений функции вызовем функцию от 1 до самого большого числа, которое встречается в вопросе (того, что стоит в print())
for i in range(1, 5102):
f(i)
# после выполнения этого цикла в памяти будут сохранены f(i), где i принимает значения от 1 до 5101 включительно.
# теперь достаточно изъять эти значения из памяти за константное время
print(f(5101) — f(5074))Второй способ решения — через списки
a = [0] * 5200
for n in range(0, 5200):
if n < 10:
a[n] = n
else:
a[n] = n**2 + a[n-9]
print(a[5101] — a[5074])[i]
Ответ: 77785554.
Задание 2 (ЕГЭ 2025, день 1)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n**2 + F(n − 1) при n > 1.
Чему равно значение выражения F(2025) − F(2022)?
[i]
from functools import *
@lru_cache(None)
def f(n):
if n == 1:
return 1
return n**2 + f(n — 1)
for i in range(1, 2026):
f(i)
print(f(2025) — f(2022))[i]
Ответ: 12289730.
Задание 3 (ЕГЭ 2025, день 1)
Алгоритм вычисления значения функции где n – натуральное число, задан следующими соотношениями:
f(n) = n, если n < 10,
f(n) = 3n-f(n-3), если n ≥ 10.
Чему равно значение выражения f(6250) + 2f(6244) / f(6238)?
В ответ запишите целую часть от получившегося значения. [i]
from sys import setrecursionlimit
setrecursionlimit(10000)
def F(n):
if n < 10:
return n
if n >= 10:
return 3*n — F(n-3)
print(F(6250)+2*F(6244)/F(6238))
[i]
Ответ: 9385.
Задание 4 (ЕГЭ 2025, день 2)
Алгоритм вычисления значения функции F(n) и G(n), где n — целое число, задан следующими соотношениями:
F(n)= 2 × (G(n − 3) + 8);
G(n)= 2 × n, если n < 10. G(n)= G(n − 2) + 1, если n ≥ 10.
Чему равно значение выражения F(15548)? [i]
from functools import *
@lru_cache(None)
def f(n):
return 2 * (g(n-3) + 8)
@lru_cache(None)
def g(n):
if n < 10:
return 2*n
return g(n-2) + 1
for i in range(1, 15549):
f(i)
g(i)
print(f(15548)) [i]
Ответ: 15588.
Задание 5 (ЕГЭ 2025, день 2)
Алгоритмы вычисления значения функции F(n) и G(n), где – целое число, заданы следующими соотношениями:
F(n) = n при n ≤ 7;
F(n) = G(n − 3) × 3, если n > 7.
G(n) = n при n ≤ 7;
G(n) = G(n − 1) + 4, если n > 7.
Чему равно значение выражения F(43000)? [i]
from functools import *
@lru_cache(None)
def f(n):
if n <= 7:
return n
return g(n-3) * 3
@lru_cache(None)
def g(n):
if n <= 7:
return n
return g(n-1) + 4
for i in range(1, 43001):
f(i)
g(i)
print(f(43000)) [i]
Ответ: 515901.
