Modern Python Standard Library Cookbook

How to do it...

Here are the steps for this recipe:

1. Python provides an LRU cache built-in, which we can use for memoization:

import functools

@functools.lru_cache(maxsize=None)
def fibonacci(n):
    '''inefficient recursive version of Fibonacci number'''
    if n > 1:
        return fibonacci(n-1) + fibonacci(n-2)
    return n

2. We can then use the function to compute the full sequence:

fibonacci_seq = [fibonacci(n) for n in range(100)]

3. The result will be a list with all the Fibonacci numbers up to the 100^th:

>>> print(fibonacci_seq)
[0, 1, 1, 2, 3, 5, 8, 13, 21 ...

The difference in performance is huge. If we use the timeit module to time our function, we can easily see how much memoizing helped with performance.

4. When the memoized version of the fibonacci ...