Автор статьи: Андрей Роженцов
В программировании на Python, особенно при решении задач с рекурсивными функциями, часто можно столкнуться с двумя проблемами: превышением максимальной глубины рекурсии и неэффективным повторным вычислением одних и тех же значений. Эти трудности не только вызывают ошибки, но и значительно увеличивают время выполнения программы. В статье мы подробно разберём, как обойти эти ограничения с помощью увеличения глубины рекурсии и двух мощных методов оптимизации: динамического программирования и кеширования. И продолжим разбор заданий ЕГЭ по информатике — 2026.
Задача 1: увеличение глубины рекурсии
def F(n): # Переписываем функцию из условия задачи
if n>3000:
return n
else:
return F(n+2)+2
print(F(40)-F(44))
При запуске программы появляется ошибка:
RecursionError: maximum recursion depth exceeded in comparison
Она означает, что превышена глубина рекурсии.
Решить эту проблему можно с помощью увеличения глубины. Для этого нам понадобится функция setrecursionlimit() из модуля sys.
import sys #импортируем модуль
sys.setrecursionlimit(3000) #устанавливаем большую глубину рекурсии — 3000
def F(n): # Переписываем функцию из условия задачи
if n>3000:
return n
else:
return F(n+2)+2
print(F(40)-F(44))
Вывод:
4
Ответ: 4
Можно пользоваться этим способом, но не во всех задачах он будет эффективен.
Рассмотрим пример функции и её вызов от значения 4.
def F(n):
if n<=1:
return n
else:
return F(n-1)+F(n-2)
print(F(4))
Программа правильно посчитает ответ. Давайте детально разберёмся, как именно.
На небольшом примере видно, что F(2) высчитывается два раза. Это происходит потому, что Python не запоминает значение функции от какого-либо аргумента, а высчитывает его заново при каждом вызове. В примере это не критично. Но если аргумент будет больше, увеличится и количество повторных действий, что повлияет на время работы программы.
Для разных значений n вызовем функцию F(n) и посмотрим, сколько раз в каждом случае высчитывается F(3). Для этого создадим глобальную переменную count и при вызове функции F(3) будем увеличивать счётчик.
def F(n):
global count # используем глобальную переменную
if n==3: # считаем, сколько раз высчитывается F(3)
count+=1
if n<=1:
return n
else:
return F(n-1)+F(n-2)
for n in range(10,20):
count = 0
print(f'n = {n}, F(n) = {F(n)}, count = {count}')
Вывод:
n = 10, F(n) = 55, count = 21
n = 11, F(n) = 89, count = 34
n = 12, F(n) = 144, count = 55
n = 13, F(n) = 233, count = 89
n = 14, F(n) = 377, count = 144
n = 15, F(n) = 610, count = 233
n = 16, F(n) = 987, count = 377
n = 17, F(n) = 1597, count = 610
n = 18, F(n) = 2584, count = 987
n = 19, F(n) = 4181, count = 1597
При вызове F(19) значение F(3) высчитывается 1597 раз. А бывают задачи, в том числе и на ЕГЭ по информатике, в которых нужно находить значение функции от гораздо больших аргументов. Поэтому разберём ещё один способ решения этой задачи.
Динамическое программирование
Динамическое программирование — метод решения задачи путём разбиения её на несколько одинаковых подзадач, связанных между собой.
В нашей задаче любое F(n), где n > 1, зависит от F(n − 1) и F(n − 2), то есть от значений функции при двух предыдущих аргументах. Тогда мы можем создать массив, в котором индекс элемента будет равен аргументу функции, а сам элемент — её значению. Например, F(0) = 10, F(1) = 15, F(2) = 27. Тогда массив F будет выглядеть следующим образом:
Перепишем код и найдём значение F(10):
F = [0,1] # запишем в массив согласно функции F(0) = 0, F(1) = 1
for n in range(2,15): # рассчитаем значения функции для чисел от 2 до 14
new_F = F[n-1]+F[n-2] # считаем новое число
F.append(new_F) # добавляем его в конец массива
print(F,F[10])
Вывод:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] 55
Ответ: 55
В этом случае каждое значение высчитывалось ровно один раз, после добавлялось в массив. Рассмотрим ещё один способ решения.
Кеширование
Кеширование — это процесс временного хранения часто используемых данных в специальном хранилище, кеше. Кеш позволит нам хранить значения функции от вызываемых аргументов, а не высчитывать их каждый раз при вызове функции. В этом нам поможет декоратор lru_cache() из встроенной библиотеки functools. Декоратор нужно писать перед тем местом, где объявляется функция.
Рассмотрим тот же пример и подсчитаем, сколько раз высчитывается F(3) при разных аргументах.
from functools import lru_cache
@lru_cache()# декоратор
def F(n):
global count # используем глобальную переменную
if n==3: # считаем, сколько раз высчитывается F(3)
count+=1
if n<=1:
return n
else:
return F(n-1)+F(n-2)
for n in range(10,20):
count = 0
print(f'n = {n}, F(n) = {F(n)}, count = {count}')
Вывод:
n = 10, F(n) = 55, count = 1
n = 11, F(n) = 89, count = 0
n = 12, F(n) = 144, count = 0
n = 13, F(n) = 233, count = 0
n = 14, F(n) = 377, count = 0
n = 15, F(n) = 610, count = 0
n = 16, F(n) = 987, count = 0
n = 17, F(n) = 1597, count = 0
n = 18, F(n) = 2584, count = 0
n = 19, F(n) = 4181, count = 0
Значение F(3) было рассчитано только один раз, при первом вызове, а потом это значение хранится в кеше и берётся оттуда. Это позволяет сильно сократить время работы и использование ресурсов компьютера.
Мы рассмотрели два способа оптимизации программы: динамическое программирование и кеширование. У каждого метода есть свои особенности, но кеширование выигрывает благодаря простой реализации и минимальным изменениям кода для решения задач.
Задача 2: две функции
Иногда в 16-м задании ЕГЭ по информатике задаются две функции, а не одна. Решение при этом ничем не отличается.
Создадим обе функции по отдельности.
from functools import lru_cache
@lru_cache() # декоратор
def F(n):
if n<3:
return 1
elif n%2==0:
return G(n)+F(n-1)
else:
return F(n-2)-2*G(n+1)
@lru_cache() # декоратор
def G(n):
if n<3:
return 1
elif n%2==0:
return F(n-3)+F(n-2)
else:
return F(n+1)-G(n-1)
print(G(120))
Вывод:
118
Ответ: 118
Задача 3: умное кеширование
from functools import lru_cache
@lru_cache()
def F(n):
if n>=3210:
return 1
else:
return F(n+3)+7
@lru_cache()
def G(n):
if n<10:
return n
else:
return G(n-3)+5
print(F(15)-G(3000))
При запуске программы получаем ошибку превышения лимита рекурсии:
RecursionError: maximum recursion depth exceeded
Почему так произошло?
Для подсчёта значения функции F(15) необходимо знать значение F(n + 3), т. е. F(18). Для подсчёта F(18) необходимо знать F(21) и т. д. Сделав некоторое количество попыток подсчитать значение функции, программа упирается в максимальный лимит рекурсии. Кеширование при этом не помогает, поскольку ни одно значение так и не было посчитано.
Добавим код:
for n in range(3212,15,-1): # Кешируем значения по убыванию
F(n)
Запустим цикл в обратную сторону, ведь F(n) = 1, где n ⩾ 3210. Значения функции F(3212), F(3211), F(3210) будут получены сразу и запомнены в кеше, а для оставшихся меньших аргументов функция будет сразу выдавать результат, т. к. любое F(n + 3) уже известно.
С функцией G всё наоборот. Так как для вычисления значения этой функции нужно знать G(n − 3), т. е. значения функции от меньших аргументов, то этот цикл запускаем от 1 до 3000.
for n in range(1,3000): # Кешируем значения по возрастанию
G(n)
Код целиком:
from functools import lru_cache
@lru_cache()
def F(n):
if n>=3210:
return 1
else:
return F(n+3)+7
@lru_cache()
def G(n):
if n<10:
return n
else:
return G(n-3)+5
for n in range(3212,15,-1): # Кешируем значения по убыванию
F(n)
for n in range(1,3000): # Кешируем значения по возрастанию
G(n)
print(F(15)-G(3000))
Вывод:
2462
Задача 4: подсчёт подходящих значений функции
from functools import lru_cache
@lru_cache()
def F(n):
if n<10:
return n
elif n<1000:
return F(n//10)+F(n%10)
else:
return F(n//1000)-F(n%1000)
count=0 # Счётчик
for n in range(10**6):
if F(n)==0: # Проверяем, что значение функции равно 0
count+=1
print(count)
Вывод:
55252
Итог
Важно правильно работать с рекурсией. Как мы увидели на примерах, простое увеличение лимита рекурсии с помощью sys.setrecursionlimit() — точечное решение и подходит не для всех случаев. Подготовка к ЕГЭ по информатике 2026 года должна включать в себя кеширование и динамическое программирование.