Recursion error while trying to write an memoization decorator

Question

This is an wrapper function that will be used to decorate the function that we want to memoize.

I wrote that as an exercise to understand how memoization works and challange myself to write it without looking at the solution.

It works, but I'm not sure if it's the best way to do it.

I got some errors while testing it with fibonacci function. I think it's because of the recursion... If you run like fib(10000) it will give you a RecursionError. But if you run fib(100) then keeping increasing the number by some reasonable amount it will work.

I'm not sure if it's because of the recursion or because of the way I wrote the memo function.

I'm still learning, so I would appreciate any feedback.

Here is the code:

def memo(fun):
    cache = {}
    def temp(*args):
        KEY = (fun, args)
        STORED_VALUE = cache.get(KEY)
        if STORED_VALUE is None:
            VALUE_TO_STORE = fun(*args)
            cache[KEY] = VALUE_TO_STORE
            return VALUE_TO_STORE
        return STORED_VALUE
    return temp

This won't work because of the recursion error RecursionError: maximum recursion depth exceeded while calling a Python object

# Fibonacci function
@memo
def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

This will work within a reasonable amount of time although I had to call it "gradually"

fib(400)
fib(800)
fib(1200)
fib(1600)
#...
# you got the point...
#...
fib(10000)

I've thought about rewriting the fibonacci function using a for loop instead of recursion, because it will not have the recursion error, but it would be computationally more simpler, not serving as a good example of memoization.

Is this just an bad example to use memoization? Or is there a way to make it work with recursion?

Zach J. · Accepted Answer · 2022-11-02T22:10:18.707

In terms of dealing with the RecursionError, I think this answer might help you out a bit.

TL;DR -

Python don't have a great support for recursion because of it's lack of TRE (Tail Recursion Elimination).

This means that each call to your recursive function will create a function call stack and because there is a limit of stack depth (by default is 1000) that you can check out by sys.getrecursionlimit (of course you can change it using sys.setrecursionlimit but it's not recommended) your program will end up by crashing when it hits this limit.

Since python doesn't have great support for that, using a for loop might work a bit better. Granted, I haven't done anything extensively in memoization so there may be a better answer out there, but that's what I'd reccomend!

Recursion error while trying to write an memoization decorator

1 Answers1