pythonfunctionrecursioncachingfibonacci

Why does the following recursive function not use the values in the cache to return the values?

I have created a python function to calculate the n-th fibonacci term. To increase the efficiency, I have used a cache_mem dict to store the variable. When I debugged the function, it is going through all function calls instead of using the stored variables of the cache. Why s this happening ?

cache_mem = {}

def fib(n):
    if n <= 1:
        return n
    else:
        cache_mem[n-1] = cache_mem.get(n-1, fib(n-1))
        cache_mem[n-2] = cache_mem.get(n-2, fib(n-2))

        return cache_mem[n-1] + cache_mem[n-2]

I expect the cache_mem dict to store the values of the results, and use them instead of calling the function. Based on my understanding, the line

cache_mem[n-1] = cache_mem.get(n-1, fib(n-1))

will check for the value for n-1 in the dict. If it exists, it will return the value, else it will calculate the values.

Solution

  • The arguments to a function are all evaluated before calling the function. So when you write

    cache_mem.get(n-1, fib(n-1))

    it first has to execute fib(n-1) before calling cache_mem.get(). So the cache never prevents making the call.

    Replace that with an explicit condition:

    if n-1 not in cache_mem:
    cache_mem[n-1] = fib(n-1)

    BTW, Python has a functools.cache decorator to add automatic caching to a function.