Decorators in Python to Improve Naive Recursive Function for Fibonacci

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
Koder Dojo
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.