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

I am a freelance, C# ASP.NET MVC Developer learning Python as well as computer science, algorithms, data structures, and data science. In addition, I am learning and developing with the new Microsoft ASP.NET Core MVC and EF Core so you will see numerous tutorials and examples of ASP.NET Core on my website. I will also be sharing my adventures on websites that offer programming challenges, like HackerRank, to encourage other developers to learn new coding skills. You can find me on twitter as @KoderDojo. Best Wishes!

Related Posts: