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 Numbersdef fib(num):if num == 0:return 0elif num == 1:return 1return fib(num - 1) + fib(num - 2)print(fib(6))
Explanation
The explanation for this code is as follows:
Line 3: It is a base case because the
Fibonacci number is also . Line 5: It is also a base case because the
Fibonacci number is . 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:
We can reduce these repetitive calls using a dynamic programming technique called memoization.
Memoization is implemented using:
Decorators in Python
The
functiontools.lru_cachefunction
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
The code for this technique is as follows:
import timeitdef memoize_fib(func):cache = {}def inner(arg):if arg not in cache:cache[arg] = func(arg)return cache[arg]return inner@memoize_fibdef fib(num):if num == 0:return 0elif num == 1:return 1else: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))
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_fibdecorator.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 functoolsimport timeit@functools.lru_cache(maxsize=150)def fib(num):if num == 0:return 0elif num == 1:return 1return 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))
Explanation
The explanation for the code above is as follows:
Line 4: It is a decorator declared in
functoolslibrary. 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.
