Рекурсия с умом: зачем кэшировать и как не утонуть в вызовах

from functools import lru_cache

@lru_cache(maxsize=None)
def g(n):
if n<=20:
return n+2
else:
return g(n-3)+1
for n in range(37812):
g(n)
print(3*g(n-3)+7)

Что делает код:
from functools import lru_cache и @lru_cache(maxsize=None):
Эти строки подключают и применяют декоратор кэширования. Он сохраняет результаты вызова функции g(n) для каждого переданного n. Это критически важно, так как без кэша рекурсивные вызовы привели бы к экспоненциальному росту времени выполнения (множество повторных вычислений одних и тех же значений). С кэшем каждое значение вычисляется ровно один раз, и сложность становится линейной.

Функция g(n):
Это прямая программная реализация математического определения функции G(n).
Если n≤20, возвращается n+2.
Если n>20, функция вызывает сама себя для n−3 и прибавляет 1.

Цикл for n in range(37812): g(n)
Этот цикл последовательно вычисляет значения функции g для всех чисел от 0 до 37811.
Зачем это нужно? В данном конкретном коде это избыточный шаг, если мы вызываем g(37808) сразу после цикла. Функция с @lru_cache сама по себе вычислит все необходимые промежуточные значения при первом вызове g(37808) (она рекурсивно спустится до базового случая).
Однако такой цикл часто пишут в задачах ЕГЭ по информатике, чтобы «прогреть» кэш или гарантировать, что все значения до нужного предела уже посчитаны, избегая даже малейшей вероятности переполнения стека при глубокой рекурсии (хотя при шаге 3 глубина для 37811 вполне допустима).
Ответ: 37861
#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_3eB0F2 #ЕГЭ_Задание16 #Рекурсия #PythonДляЕГЭ #ИнформатикаСНуля #functools_import_lru_cache