How to properly use the Decorator pattern to add Memoization to recursive algorithms in Python?

I am learning about Dynamic Programming and I've implemented a recursive algorithm to solve the "Climbing Stairs" problem (which is essentially finding the N-th Fibonacci number).

The basic recursive version works for small inputs, but it becomes extremely slow for $N > 35$ due to redundant calculations. I know that I can use Memoization to optimize this, but I want to keep the core logic of my algorithm "clean" without mixing the caching logic with the calculation logic.

Research I've done:

I found that functools.lru_cache exists in Python and it solves the problem perfectly.

However, for educational purposes, I want to implement my own Decorator to understand the Architectural Pattern behind it.

I've seen examples of function decorators, but I'm confused about how they handle the scope of the memo dictionary across multiple recursive calls.

Here is my current "clean" but slow implementation:

def count_stairs(n): # Base cases if n <= 1: return 1 # Recursive step return count_stairs(n - 1) + count_stairs(n - 2) # Problem: This takes several seconds for n=35 print(count_stairs(35))

What I'm trying to achieve:

I want to create a decorator called @memoize so I can just write:

@memoize def count_stairs(n): ...

The Problem: I've tried writing a simple decorator, but I keep getting NameError or the cache seems to reset on every call because I'm not sure where to store the dictionary. Should the cache be a global variable, or is there a way to encapsulate it within the decorator's closure to follow better Software Architecture principles?

Could someone show the "correct" way to implement this architectural shift from a simple recursion to a decorated one?