In this tutorial we are going to look at a concept in computer science called memoization
. This is a really cool concept that allows us to optimize the runtime performance of some of our recursive algorithms by effectively caching the results of previous computations so that they don’t have to be continuously recomputed.
The Fibonacci Example
Calculating Fibonacci in a recursive manner is quite possibly the best example I’ve come across when it comes to showing the power of memoization
.
Imagine we had a function that computed the fibonacci number n
like so:


When we then tried to run our fib(7)
function it would then compute the following answer.


Now the runtime complexity of this relatively simple function above would be O(2^n)
which is incredibly inefficient as we start to compute larger and larger fibonacci numbers.
The Memoization Optimization
Through the use of memoization
we could effectively store the results of previous computations. In order to store our results we will use a dict
in Python.


When you run this you should get the following output. As you can see from the number of times Memo Computed
is printed out, we have been able to effectively optimize the number of times we have to recursively call fib()
.


We have been able to modify our program and change is runtime performance from O(2^N)
to O(N)
which is a huge saving.
Entire Program
The entire Python file can be found below.


The outputs of this are:


As you can see the memoized
version of the fibonacci function returns in a fraction of the time.
Conclusion
If you found this tutorial useful or need further explanation then please feel free to let me know in the comments section below!