How to do memoization in Python

Recursion is a technique in which a function repeatedly calls itself until a base case (termination condition) is met. It breaks the problem into smaller sub-problems and calls itself until it reaches the slightest problem (solution already known; for example, factorial(1) = 1) is also known as the base case.

What is memoization?

Memoization is a top-down dynamic programming approach in which the results of all the recursive calls are recorded/cached. If the function is again called with the same parameters, it uses the stored results to avoid repeated calculations and speed up the program.

In this Answer, we will use the example of the Fibonacci series to explain the concept of repeated calculations using recursion.

Recursion code

The recursive code used to calculate a Fibonacci number is as follows:

# Fibonacci Numbers
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fib(num - 1) + fib(num - 2)
print(fib(6))
Recursive code for calculating a Fibonacci number.

Explanation

The explanation for this code is as follows:

  • Line 3: It is a base case because the 0th0^{th}Fibonacci number is also 00.

  • Line 5: It is also a base case because the 1st1^{st}Fibonacci number is 11.

  • Line 7: It makes two recursive calls to calculate the last two Fibonacci numbers, adds them both, and returns this number.

This code is not very efficient because we are making too many repetitive recursive calls with the same inputs, as shown in the diagram below:

All the highlighted blocks are duplicated.

We can reduce these repetitive calls using a dynamic programming technique called memoization.

Memoization is implemented using:

  • Decorators in Python

  • The functiontools.lru_cache function

Decorator in Python

A cache is used to store the data in the code snippet below. If the required data is already computed, it returns its output. Otherwise, it calls the required function:

def memoize_fib(func):
    cache = {}
    def inner(arg):
        if arg not in cache:            
            cache[arg] = func(arg)
        return cache[arg]
    return inner
Code for a decorator in Python

Code

The code for this technique is as follows:

import timeit
def memoize_fib(func):
    cache = {}
    def inner(arg):
        if arg not in cache:            
            cache[arg] = func(arg)
        return cache[arg]
    return inner
    
@memoize_fib
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fib(num-1) + fib(num-2)
print( "30th Fibonacci number is:",fib(30))
print("Time taken to run this function is:",timeit.timeit('fib(30)', globals=globals(), number=1))
Implementing memoization technique using decorators in Python.

Explanation

  • Lines 3–9: We define a function that will later be used as a decorator. It caches the result of our previous function calls, and if the result is already present in the cache, then it returns that result.

  • Line 11: It declares that the following function must be used with the memoize_fib decorator.

  • Lines 12–18: We define a normal recursive function to calculate a Fibonacci number.

Note: The timeit() function calculates the execution time for our code. For more information, click ​here.

The functiontools.lru_cache function in Python

It is a built-in decorator that is available in the functools library of Python. It uses the memoization technique to reduce the execution time of a function.

Code

The code for this technique is as follows:

import functools
import timeit
@functools.lru_cache(maxsize=150)
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fib(num - 1) + fib(num - 2)
print("30th Fibonacci number is:", fib(30))
print("Time taken to run this function:", timeit.timeit('fib(30)', globals=globals(), number=1))
How to calculate Fibonacci numbers using functools.lru_cache function.

Explanation

The explanation for the code above is as follows:

  • Line 4: It is a decorator declared in functools library. It caches the results from previous function calls and returns that result if the function is called with the same parameters again.

  • Lines 5–10: Defines a simple recursive function to calculate a Fibonacci number.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved