Today, let’s explore how to implement memoization techniques to optimize the performance of recursive functions in Python.

A recursive function is a function which calls itself. Recursive functions are used to solve programming problems which are recursive in nature, like the tower of Hanoi. Recursive functions reduce code clutter, avoid unnecessary function calls and are commonly used for solving data structure problems.

The efficiency and speed of recursion may be effected if you have a deep hierarchy of recursive function calls. For cases like this, you can optimize your recursive functions using memoization techniques which we’ll explore in this tutorial.

Optimization Issue with Recursive functions

Let’s define a simple recursive function which returns the “Nth” number from a Fibonacci series. A Fibonacci series starts from two digits, 0 and 1, and every next number in the series is the sum of the previous two numbers. For example the first 10 numbers in the Fibonacci series (excluding 0) are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

def find_fibonnaci(n):

    if n == 1:
        return 1

    elif n == 2:
        return 1

    elif n > 2:
        return find_fibonnaci(n - 1) + find_fibonnaci(n - 2)

Here’s what’s happening in the above function. Since the first 2 numbers in a Fibonacci series are 1 (excluding 0), the find_fibonnaci() function returns 1 if n is 1 or 2. Else, if n is greater than 2, recursion takes place and the sum of find_fibonnaci(n-1) and find_fibonnaci(n-2) is returned.

So how does this recursion find the Fibonacci number?

Suppose you want to find the 4th number in the Fibonacci series, you can find it as follows. We’ll call this equation 1.

find_fibonnaci(4) = find_fibonnaci(3) + find_fibonnaci(2)  --- equation 1

Since, find_fibonnaci(2) will return 1, and find_fibonnaci(3) will return find_fibonnaci(2) + find_fibonnaci(1), equation 1 can be rewritten as follows:

find_fibonnaci(4) = (find_fibonnaci(2) + find_fibonnaci(1)) + 1 --- equation 2

We’ll call this equation 2.

If you replace values of find_fibonnaci(1), and find_fibonnaci(2) in equation 2, you’ll get the answer of find_fibonnaci(4):

find_fibonnaci(4) = 1 + 1 + 1

find_fibonnaci(4) = 3

Alright, let’s call our find_fibonnaci() function to see if it works:

find_fibonnaci(4)

The output shows the correct result.

Output:

3

Our function works well so let’s try printing the first 10 numbers of the Fibonacci series:

for i in range(1,11):
    print(i, "-", find_fibonnaci(i))

The output shows the first 10 numbers in the Fibonacci series printed pretty quickly on the console.

Output:

1 - 1
2 - 1
3 - 2
4 - 3
5 - 5
6 - 8
7 - 13
8 - 21
9 - 34
10 - 55

Okay, so far so good. Let’s try a bigger number. For example, lets print the first 40 numbers in the Fibonacci series and we’ll time how long it takes to run.

Note: The script below is run in the Jupyter notebook. To find the cell execution time for the script, the %%time command is used. We published a full tutorial about how to find the execution time of a Python script.

%%time
for i in range(1,41):
    print(i, "-", find_fibonnaci(i))

For the sake of space, only Fibonacci numbers from 30 to 40 are printed:

Output:

30 - 832040
31 - 1346269
32 - 2178309
33 - 3524578
34 - 5702887
35 - 9227465
36 - 14930352
37 - 24157817
38 - 39088169
39 - 63245986
40 - 102334155
Wall time: 1min 23s

The output shows that it took a whopping 1 minute and 23 seconds to calculate the first 40 numbers in a Fibonacci series. This is a significant amount of time and this happens as a direct result of the large number of hierarchical recursive calls.

Let me explain. To calculate find_fibonnaci(40), you have to calculate find_fibonnaci(39) and find_fibonnaci(38) upto find_fibonnaci(1). The number of function calls grow exponentially which significantly slows down the overall Python calculation.

This is where memoization comes in. With memoization, you can save previous function calls in a cached memory and then when a new calculation has to be performed the result of previous function calls can be used instead of making new function calls from scratch. Memoization can be implemented via custom Python code or via a built-in Python module. We’ll demonstrate both methods.

Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit

Memoization via Custom Python Code

To implement custom memoization, you need to create a data structure, like a dictionary, which acts as a cache and stores results of any previous calls to a recursive function. Then when a recursive function is called, you first check if the result of that call already exists in the cache, in which case you simply return the result from the cache instead of calling the function again. Else, you call the function and store the result in the cache before returning it to the calling function, which can then be used for later function calls. It sounds complicated, but it’s not so bad.

The following script implements memoization for a function that returns numbers in the Fibonacci series.

my_cache = {}

def find_fibonnaci_cached(n):

    # creating custom cache
    if n in my_cache:
        return my_cache[n]

    if n == 1:
        result = 1

    if n == 2:
        result = 1  

    elif n > 2:
        result = find_fibonnaci_cached(n - 1) + find_fibonnaci_cached(n - 2)

    my_cache[n] = result

    return result

Let’s now see how long it takes to print the first 40 Fibonacci numbers using the find_fibonnaci_cached() function which implements memoization.

%%time
for i in range(1,41):
    print(i, "-", find_fibonnaci_cached(i))

Output:

30 - 832040
31 - 1346269
32 - 2178309
33 - 3524578
34 - 5702887
35 - 9227465
36 - 14930352
37 - 24157817
38 - 39088169
39 - 63245986
40 - 102334155
Wall time: 4.99 ms

The output shows that it only took 4.99 ms which is lightning fast compared to the 1 minute and 23 seconds it took without memoization.

Let’s now try to find how long it takes to print the first 1000 Fibonacci numbers.

%%time
for i in range(1,1000):
    print(find_fibonnaci_cached(i))

Output:

# first 1000 fibonnaci numbers will be printed
Wall time: 334 ms

The result shows that it took only 334 ms seconds to print the first 1000 Fibonacci numbers using memoization!

Memoization via Python functools module

Instead of implementing custom memoization, you can use the lru_cache decorator from the Python functools module to cache the result of a specific number of calls to a function. The number of calls to cache are specified via the maxsize attribute of the lru_cache decorator. Here’s an example where we cache 1000 calls to the find_fibonnaci() method.

from functools import lru_cache

@lru_cache(maxsize = 1000)
def find_fibonnaci(n):

    if n == 1:
        return 1

    elif n == 2:
        return 1

    elif n > 2:
        return find_fibonnaci(n - 1) + find_fibonnaci(n - 2)

Let’s see how much time it takes to print the first 1000 Fibonacci numbers using Python’s built-in memoization.

%%time
for i in range(1,1000):
    print(find_fibonnaci(i))

Output:

# first 1000 fibonnaci numbers
Wall time: 68 ms

The output shows that it took only 68 ms seconds to print the first 1000 Fibonacci numbers using memoization, which is even faster than our custom memoization!

If you found this tutorial fascinating, join us using the form below and we’ll share a few more Python tips and tricks to help you get the most out of this powerful programming language.

Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit