Recursion & Memoization In Python
4 min readRecursion can be a dirty word in programming. It gets a bad wrap for good reasons like stack overflows and infinite loops. In this post we will look at the Fibonacci sequence and how we can apply recursive concepts to solve it. We will then look at how horribly inefficient this solution is and how the concept of memoization can drastically improve that efficiency.
The Problem
The Fibonacci sequence, in case you have not heard of it, is a mathematical sequence where a number is the sum of the two previous numbers before it.
0 1 1 2 3
So looking at these numbers 1 is the sum of 0 + 1
and 2 is the sum of 1 + 1
and so on and so forth.
Enter Recursion
Recursion is when we call a function from within itself. With recursion we need to think in terms of our terminating case first, so at what point should our recursive function call end. We think in these terms to avoid entering an infinite loop since we will be calling the function from inside itself. In the case of fibonacci when we have made it to the last two numbers, 0 and 1, we have made it to our terminating case. We can check for this through the following conditional:
if n < 2:
return n
So our function will start off looking as:
def fib(n):
if n < 2:
return n
Now since we know that fibonacci is the sum of the two previous numbers we can call our fib()
and add the two calls together where we are taking one less and two less n
as the inputs for each iteration:
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
Executing Fibonacci
When we run our fib
function we can see that it works with no issues with smaller numbers. Running fib(8)
returns relatively quickly; however if we run fib(40)
we will be waiting for a hot minute for the return value. This is due to the fact that we are processing a lot of the same computation over and over again. For example let’s look at fib(5)
:
Pass 1: fib(4) + fib(3)
Pass 2: fib(3) + fib(2)
Pass 3: fib(2) + fib(1)
Pass 4: fib(1) + fib(0)
So looking at the above diagram we can see that we run the computation of fib(3)
twice as well as other instances. If we have ran and know the value of this computation already it becomes redundant to process it over an over again.
Enter Memoization
Memoization is a manner in which we can cache our results and then check to see if we have seen that function call before.
def memoize(fn):
cache = {}
def helper(x):
# If not in our cache store it.
if x not in cache:
cache[x] = fn(x)
# else return the cached function call.
return cache[x]
return helper
Now when using memoization with our fib()
our diagram changes to look like the following:
Pass 1: fib(4) + fib(3)
Pass 2: value of fib(3) + fib(2)
Pass 3: value of fib(2) + fib(1)
Pass 4: value of fib(1) + fib(0)
We get this instead because we have stored the return value from fib(n)
at the specified key in our cache.
Using our memoization function
There are two ways to use this function in Python. We can just supply fib
to it and reassign fib
or we can use the decorators feature:
fib = memoize(fib)
fib(40)
@memoize
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
Now when running fib(40)
we see a nearly instant return in the terminal just like we had seen before with lower input values. Memoization is a great way to increase the performance of a recursive function.
Related Articles
Python Scripting In iTerm2
How to use the Python Scripting API in iTerm2 to open several tabs and execute commands in those tabs.
Writing A Connect Four Game Reader In Python
Writing a program that will read moves and populate a game board for the popular game Connect Four using Python.
Getting Started With Python3
Installation and setup of Python3 on macOS & development with Visual Studio Code.
Building A Black Jack Advice Generator With Python
How to build a simple black jack advice generator using Python.
Cody is a Christian, USN Veteran, Jayhawk, and an American expat living outside of Bogotá, Colombia. He is currently looking for new opportunities in the tech industry.