Implementation

Python decorators are generic and very powerful. You can find many examples of how they can be used at the decorator library of python.org [j.mp/pydeclib]. In this section, we will see how we can implement a memoization decorator [j.mp/memoi]. All recursive functions can benefit from memoization, so let's pick the popular Fibonacci sequence example. Implementing the recursive algorithm of Fibonacci is straight forward, but it has major performance issues, even for small values. First, let's see the naive implementation (file fibonacci_naive.py).

def fibonacci(n):
    assert(n >= 0), 'n must be >= 0'
    return n if n in (0, 1) else fibonacci(n-1) + fibonacci(n-2)

if __name__ == '__main__':
    from timeit import Timer
    t = Timer('fibonacci(8)', 'from __main__ import fibonacci')
    print(t.timeit())

A sample execution of this example shows how slow this implementation is. It takes 17 seconds to calculate the eighth...