Understanding Python decorators optimizing a recursive Fibonacci implementation

A decorator is a Python function that takes a function object as an argument and returns a function as a value. Here is an example of decorator definition:

To apply a decorator to an existing function, you just need to put @decorator_name in the line before its definition, like this example:

This decorator doesn’t do anything, so let’s think about a more concrete problem we could solve using decorators.

Fibonacci sequence

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1 or 0 and 1. All the other numbers are the sum of the previous two numbers of the sequence. Example:

  1. 0, 1: the third number is 1
  2. 0, 1, 1: the fourth number is 2
  3. 0, 1, 1, 2: the fifth number is 3
  4. 0, 1, 1, 2, 3: the sixth number is 5
  5. etc…

If we wanted to give a math definition of the sequence, we could describe it in this way:

  • F(0): 0
  • F(1): 1
  • F(n): F(n-1) + F(n-2)

In Python we could have a recursive function like the following one:

What’s the problem with this implementation? The code works as expected, but it’s very inefficient. The next picture will explain what happens when we will try, for example, to calculate the 5th number of the sequence:

fibo

 

Fib(5) is Fib(4) + Fib(3), but Fib(4) itself is Fib(3) + Fib(2), and… the picture just tell us that we have calculated Fib(3) 2 times, Fib(2) 3 times, Fib(1) 5 times! Why are we repeating the same operation every time if we already calculated the result?

Memoization

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

We need to store values of the sequence we have already calculated and get them later when we need them. Let’s implement a simple memoization decorator:

The decorator defines a dict at the beginning that is used as a cache. When we want to find the n number of the sequence, it first checks if the value was already calculated and that value is returned instead of being calculated again. If the value is not found, then the original function is being called and then the value is store in the cache, then returned to the caller.

Using the memoize decorator

How much this decorator can speed up our fib method? Let’s try to benchmark the execution using Python timeit module.

The required time to calculate the 35th number of the Fibonacci sequence on my laptop is: 4.73480010033

The required time to calculate the 35th number of the Fibonacci sequence on my laptop is: 0.000133037567139

Quite faster, don’t you think? I will let you try how long does it take to calculate the 60th number of the sequence with and without using the decorator. Hint: grab a cup of coffee before beginning!