Memoization and the Fibonacci Sequence

This is a note on using memoization with recursion - specifically with the generation of a Fibonacci Number. The fibonacci numbers form a sequence where

\[ F_0 = 0, F_1 = 1 \]

and then for the rest of the numbers greater than 1

\[ F_n = F_{n-1} + F_{n-2} \]

So, starting from 0 you get 0, 1, 1, 2, 3, 5, 8, etc.

Calculating the sequence is often done with recursion because you can pretty much take the definition and convert it to a function with little translation.

def fibonacci(n: int) -> int:
    """Calculates the n-indexed fibonacci number

    Args:
     n: the index of the number in the (zero-based) sequence to get

    Returns:
     fibonacci number at index n
    """
    assert n >= 0
    if n < 2:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

expected = 55
actual = fibonacci(10)
print(actual)
assert expected == actual, actual

55

Remember that n is the index for number, not the count (the second number in the sequence has index 1).

The problem here is that recursion like this has memory limits and takes a long time.

from graeae import Timer
TIMER = Timer()

expected = 102334155
n = 40
with TIMER:
    actual = fibonacci(n)
    print(n)
    assert actual == expected, actual

2020-11-09 21:11:05,852 graeae.timers.timer start: Started: 2020-11-09 21:11:05.852071
2020-11-09 21:11:50,249 graeae.timers.timer end: Ended: 2020-11-09 21:11:50.249808
2020-11-09 21:11:50,251 graeae.timers.timer end: Elapsed: 0:00:44.397737
40

Less than a minute might not seem like a big deal, but even pushing it up to 45 makes the wait too long (I gave up and killed the process so I don't know how long it ran). So what's the solution? Let's try memoization.

So, what's memoization? Is it what Elmer Fudd does when he memorizes? No, memoization comes from the latin word memorandum which means "to be remembered". What we're going to do is create a cache dictionary that will match arguments to our function call to their outputs. Then if a function call comes in that uses arguments that were used before, we can just grab it from the cache instead of re-doing the calculations.

We're going to use a python decorator from functools named wraps that allows you to build a decorator that looks like the original function. It isn't necessary for the decorator to work, but it makes it look more like the original functior passed to the decorator so it's a good practice to use it.

from functools import wraps

def memoize(function):
    """Adds caching

    Args:
     function: the callable to memoize

    Returns:
     callable with caching and the original function
    """
    cache = {}
    @wraps(function)
    def wrapped(*args):
        if args not in cache:
            cache[args] = function(*args)
        return cache[args]
    return wrapped

Although it works as a decorator, since we already defined the fibonacci function we can just pass it to memoize to add the cache.

fibonacci = memoize(fibonacci)

Now let's see what happens.

with TIMER:
    actual = fibonacci(100)
print(actual)

2020-11-10 15:45:08,117 graeae.timers.timer start: Started: 2020-11-10 15:45:08.117332
2020-11-10 15:45:08,118 graeae.timers.timer end: Ended: 2020-11-10 15:45:08.118691
2020-11-10 15:45:08,120 graeae.timers.timer end: Elapsed: 0:00:00.001359
354224848179261915075

Note: I originally tried renaming the memoized function, but since the recursive calls go to the original function name, this doesn't produce and improved function. You have to use the same name as you did when you defined the function.

So memoization really helps, even more than you might expect. The reason why is that the first recursion term (fibonacci(n - 1)) gets evaluated first, so each recursive call goes backwards by one until it hits the base-case where n < 2 and then all the rest of the calls are evaluated, but after one run through the indexes you've already hit all the cases you need for these other calls so rather than making more recursive calls, everything gets pulled from the cache.

As is often the case, when you implement something useful in python you'll find that it's already been implemented, in this case as part of the python standard library.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_o_nacci(n: int) -> int:
    """Calculates the n-indexed fibonacci number

    Args:
     n: the index of the number in the (zero-based) sequence to get

    Returns:
     the nth fibonacci number
    """
    assert n >= 0
    if n < 2:
        return n

    return fib_o_nacci(n - 1) + fib_o_nacci(n - 2)

Note: in python 3.9 there is a cache decorator that is the same thing as the lru_cache with maxsize=None but I'm running this on python 3.8 right now so I can't use it.

with TIMER:
    print(fib_o_nacci(500))

2020-11-09 21:53:19,405 graeae.timers.timer start: Started: 2020-11-09 21:53:19.405955
2020-11-09 21:53:19,407 graeae.timers.timer end: Ended: 2020-11-09 21:53:19.407891
2020-11-09 21:53:19,409 graeae.timers.timer end: Elapsed: 0:00:00.001936
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Okay, so, I think it works, although I'm not checking the values, the speed seems to be an improvement.