Fibonacci Function Memoization in Python

Question

I'm working on a problem in codewars that wants you to memoize The Fibonacci sequence. My solution so far has been:

def fibonacci(n):  
    return fibonacci_helper(n, dict())

def fibonacci_helper(n, fib_nums):
    if n in [0, 1]:
        return fib_nums.setdefault(n, n)

    fib1 = fib_nums.setdefault(n - 1, fibonacci_helper(n - 1, fib_nums))
    fib2 = fib_nums.setdefault(n - 2, fibonacci_helper(n - 2, fib_nums))

    return fib_nums.setdefault(n, fib1 + fib2)

It works reasonably well for small values of n, but slows down significantly beyond the 30 mark, which made me wonder — is this solution even memoized? How would I get this type of solution working fast enough for large values of n?

Answer 1

Your function isn't memoized (at least not effectively) because you call fibonacci_helper regardless of whether you already have a memoized value. This is because setdefault doesn't do any magic that would prevent the arguments from being evaluated before they're passed into the function -- you make the recursive call before the dict has checked to see whether it contains the value.

The point of memoization is to be careful to avoid doing the computation (in this case a lengthy recursive call) in cases where you already know the answer.

The way to fix this implementation would be something like:

def fibonacci(n):  
    return fibonacci_helper(n, {0: 0, 1: 1})

def fibonacci_helper(n, fib_nums):
    if n not in fib_nums:
        fib1 = fibonacci_helper(n-1, fib_nums)
        fib2 = fibonacci_helper(n-2, fib_nums)
        fib_nums[n] = fib1 + fib2
    return fib_nums[n]

If you're allowed to not reinvent the wheel, you could also just use functools.lru_cache, which adds memoization to any function through the magic of decorators:

from functools import lru_cache

@lru_cache
def fibonacci(n):
    if n in {0, 1}:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

You'll find that this is very fast for even very high values:

>>> fibonacci(300)
222232244629420445529739893461909967206666939096499764990979600

but if you define the exact same function without the @lru_cache it gets very slow because it's not benefitting from the cache.

>>> fibonacci(300)
(very very long wait)