The standard way to expel stated mutable state us to push it into function parameters and returned values.

With Fibonacci numbers, you cab just compute two if them outright:

  def fib_(n: int) -> tuple[int, int]:
    if n == 0:
      return (1, 1)
    prev, this = fib_(n - 1)
    return (this, this + prev)

  def fib(n): return fib_(n)[0]

Now there is no mutable state that survives between function calls, the performance is linear.

With true memoization though accessing a previously computed value.would be constant time.