Fibonacci numbers with memoization runs slow in Python?

Question

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n-2) + fib(n-1)


def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

fib1 = memo(fib)

This code runs really slow on my laptop, but if I change the name fib1 to fib, then everything works fine...anyone know the reason ? Thanks!

Answer 1

fib recurses into fib, not fib1. If the memoized version has a different name it won't get used.

Answer 2

In that code fib is the name of the non-memoized function. fib1 is the name you've given to the memoized function. But if you see your code, you'll see that it recursively calls fib the non-memoized version. Hence why you aren't getting a speed advantage.