Fibonacci numbers have been used a lot by my computer science and algorithms professors to demonstrate recursive functions and performance differences among algorithms. The naive recursive versions of calculating Fibonacci numbers is the one you see the most:

def fib(n): """ Returns the n'th Fibonacci number where n is an integer >= 0 :param n: integer >= 0 :return: n'th Fibonacci number """ if n < 2: return n return fib(n - 1) + fib(n - 2)

In my articles I have improved and played with Fibonacci numbers using Dynamic Programming, Fibonacci generators, and recently I talked about using memoization to improve the performance of generating Fibonacci numbers. Here is the example that uses memoization to improve the performance of the recursive function by caching previous Fibonacci numbers.

def fib(n): def fib_memo(n, m): """ Find the n'th fibonacci number. Uses memoization. :param n: the n'th fibonacci number to find :param m: dictionary used to store previous numbers :return: the value of the n'th fibonacci number """ if n in m: return m[n] answer = fib_memo(n - 1, m) + fib_memo(n - 2, m) m[n] = answer return answer m = {0: 0, 1: 1} return fib_memo(n, m)

Recently I learned about decorators in Python, which made me realize this memoization can be done using a Python decorator.

## Python Decorator for Memoization

Here is a `memoize`

decorator in Python. I added some print statements to it for this Fibonacci example so it is clear as to what is happening in the decorator.

import collections import functools def memoize(function): cache = {} @functools.wraps(function) def wrap(*args, **kwargs): if not isinstance(args, collections.Hashable): return function(*args, **kwargs) if args in cache: print('returning fib({}) from cache.'.format(*args)) return cache[args] print('calling fib({})'.format(*args)) value = function(*args, **kwargs) print('adding fib({}) to cache'.format(*args)) cache[args] = value return value return wrap @memoize def fib(n): """ Returns the n'th Fibonacci number where n is an integer >= 0 :param n: integer >= 0 :return: n'th Fibonacci number """ if n < 2: return n return fib(n - 1) + fib(n - 2) for i in range(20): print(fib(i), end='\n\n')

Here is some sample output when run.

calling fib(0) adding fib(0) to cache 0 calling fib(1) adding fib(1) to cache 1 calling fib(2) returning fib(1) from cache. returning fib(0) from cache. adding fib(2) to cache 1 calling fib(3) returning fib(2) from cache. returning fib(1) from cache. adding fib(3) to cache 2 calling fib(4) returning fib(3) from cache. returning fib(2) from cache. adding fib(4) to cache 3 calling fib(5) returning fib(4) from cache. returning fib(3) from cache. adding fib(5) to cache 5

Using a Python decorator that caches previous results is both a great example of a decorator, but also a great way to separate out cross-cutting concerns like caching, logging, etc. Turns out a Python decorator like this already exists in `functools`

, called `lru_cache`

.

## functools.lru_cache for Memoization in Python

If you have a function in Python that can be improved by using memoization, there is a decorator in the `functools`

module, called `lru_cache`

. You can use `@lru_cache`

similar to using the custom `@memoize`

Python decorator I created above.

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): """ Returns the n'th Fibonacci number where n is an integer >= 0 :param n: integer >= 0 :return: n'th Fibonacci number """ if n < 2: return n return fib(n - 1) + fib(n - 2) for i in range(10): print(fib(i), end=', ') # 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

I hope this is useful. You can find me on twitter at @koderdojo.

**Posted by David Hayden**