Как правильно использовать шаблон «Декоратор» для добавления мемоизации в рекурсивные алгоритмы Python? ⇐ Python

[Anonymous]

Я изучаю динамическое программирование и реализовал рекурсивный алгоритм для решения задачи «Подъем по лестнице» (которая, по сути, заключается в нахождении N-го числа Фибоначчи).
Базовая рекурсивная версия работает для небольших входных данных, но при $N > 35$ она становится чрезвычайно медленной из-за избыточных вычислений. Я знаю, что могу использовать Мемоизацию для оптимизации этого, но я хочу, чтобы основная логика моего алгоритма была «чистой», не смешивая логику кэширования с логикой вычислений.
Проведенные мной исследования:

• Я обнаружил, что functools.lru_cache существует в Python и прекрасно решает проблему.
• Однако в образовательных целях я хочу реализовать свой собственный Декоратор, чтобы понять лежащий в его основе Архитектурный шаблон.
• Я видел примеры декораторов функций, но меня смущает, как они обрабатывают область словаря memo при нескольких рекурсивных вызовах.

Вот моя текущая «чистая», но медленная реализация:

Код: Выделить всё

def count_stairs(n):
# Base cases
if n