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!

Add some prints to your fib() function and see if the calls make sense to you. — Russell Borogove, Mar 09 '12 at 02:35
A nice way to do this is with decorators: http://ujihisa.blogspot.com/2010/11/memoized-recursive-fibonacci-in-python.html — Hooked, Mar 09 '12 at 02:41

score 5 · Accepted Answer · answered Mar 09 '12 at 02:40

5

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

answered Mar 09 '12 at 02:40

Mark Ransom

299,747
42
398
622

score 2 · Answer 2 · answered Mar 09 '12 at 02:39

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.

score 1 · Answer 3 · edited May 23 '17 at 11:49

In python 3 you can achieve your goal by using nonlocal as pointed out here.

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

Python's functools module provides decorators that accomplish caching. There is a limit to these approaches in that they add cost to the total recursion depth. An alternate approach using closures allows for deeper recursion.

def fibonacci(n):
    cache = {0:0,1:1}
    def fib(n):
        if n in cache:
            return cache[n]
        cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
    return fib(n)

score 1 · Answer 4 · answered Mar 09 '12 at 02:52

I agree that adding some prints you would probably see the issue. You're very close to actually getting it.

What you have right now only stores n where n is the argument given to fib1. Inside fib, you're calling fib which won't memoize any previously computed values. So by adding a print statement to fib print "fib ", n and calling fib1(4), you will get the following output:

fib 4
fib 2
fib 3
fib 1
fib 2

So you see it calls fib with n=2 twice. The reason why fib = memo(fib) is faster is because then it's actually momoizing because you're redefining fib to be the memoized function.

Fibonacci numbers with memoization runs slow in Python?

4 Answers4

Linked