🔥 Оптимизируем рекурсию: считаем F(15) с мемоизацией! 🔥

Сегодня разберём крутой приём, который делает рекурсивные функции в разы быстрее — мемоизацию. Смотри, как это выглядит в коде: 👇

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
if n < 3:
return 1
if n % 2 == 0:
return f(n - 2) - f(n - 1)
return 2 * f(n - 1) - f(n - 2)

print(f(15))

🤔 Что тут происходит?

from functools import lru_cache — импортируем декоратор для кэширования результатов. Это как «записная книжка» для функции: она запоминает, что уже посчитала, и не тратит время на повторные вычисления.
@lru_cache(maxsize=None) — вешаем декоратор на функцию. Параметр maxsize=None означает, что ограничений по количеству сохранённых результатов нет — функция может запомнить сколько угодно значений.
if n < 3: return 1 — базовый случай рекурсии. Это «стоп-сигнал», без которого функция уходила бы в бесконечный цикл.
if n % 2 == 0: return f(n - 2) - f(n - 1) — для чётных n используем формулу из условия задачи.
return 2 * f(n - 1) - f(n - 2) — для нечётных n применяем вторую формулу.
print(f(15)) — запускаем функцию и выводим результат.

🚀 Почему это круто?

Без мемоизации при больших n функция многократно пересчитывает одни и те же значения — это сильно замедляет работу. С @lru_cache каждое значение считается только один раз, а потом просто берётся из кэша. Это как выучить таблицу умножения вместо того, чтобы каждый раз складывать числа! 😄

💡 Полезный факт: lru_cache использует стратегию LRU (Least Recently Used) — если бы мы задали конкретный maxsize, то при его превышении из кэша удалялись бы самые старые или наименее используемые значения. Но в нашем случае мы не ограничиваем размер кэша, чтобы сохранить все результаты.

Хочешь ещё больше лайфхаков по оптимизации кода, разборов алгоритмов или задач на рекурсию? Подписывайся на канал — впереди ещё куча интересного! 😉🔔

#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_859446 #ЕГЭ_Задание16 #Рекурсия #PythonДляЕГЭ #ИнформатикаСНуля #functools_import_lru_cache