memoization question - My memo dict performs better than lru

I have been playing with memorization and lru_cache... I have a quick question as to why my memoization code runs better than lru_cache.

My code:

memo = {}
def fib(n): 
    if n == 0:
        return 0
    elif n < 2: 
        return 1
    else:
        if n not in memo:
            memo[n] = fib(n-1)   fib(n-2)
    return memo[n]
print(fib(900))

lru_cache code:

from functools import lru_cache


@lru_cache(maxsize=1000)
def fib(n):
    if n == 0:
        return 0
    elif n < 2:
        return 1
    else:
       return fib(n -1)   fib(n -2)
    
    
print(fib(499))

The second I try to find the 500th fib number, I get the following error with lru_cache:

lk/Documents/VSCode/testing_zone/fibonacci_examples/fib_with_lru_cache.py
Traceback (most recent call last):
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 14, in <module>
    print(fib(500))
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1)   fib(n -2)
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1)   fib(n -2)
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1)   fib(n -2)
  [Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded

Yet on my simple dict memoization I can go up to 900 before I run into the same error

lk/Documents/VSCode/testing_zone/fibonacci_examples/fib_with_memo.py
54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800

My understanding is that both the dict and the lru_cache operate in the same way where they reference the dict or lru_cache to see if n is in them before recalling the fib(n) function.

My question is why are they not performing the same? Have I misconfigured the code or is there additional optimizations/code I need to use with lru_cache?

lru_cache must be working, as fib(400) is returned almost instantly, which wouldn't happen if the decorator was not there.

CodePudding user response：

Your precise problem is that @lru_cache introduces a second function call. It literally puts a wrapper around the function fib.

When you think you're calling fib, you're actually calling the wrapper program. It looks to see if the value is in its cache. If so, it returns the value; if not, it calls the saved original definition of fib, puts the returned value in its cache, and then returns that value.

So when you call fib(500), your function call depth is 1000. Your memoization program has inlined its cache into the function body, so the call depth is only 500. Hence the error about maximum recursion.

You can find out the current recursion limit using sys.getrecursionlimit(). You can modify the limit using sys.setrecursionlimit().