1. Python

Memoization in Python

Memoization word is derived from latin word memorandum which means to be remembered. That’s meaning of word Memoization in terms of common English language, but what’s meaning in Python? In Python, memoization is remembering results of computations like function calls.

If your doing some computation let’s say adding all of elements in list of length 10000, doing this addition would be very expensive and will be taking a lot of time. So rather than calculating again and again, just store computed value in some form into program and refer to that form whenever sum of all elements in list is needed.

Let’s try to understand this concept of Memoization in Python by taking an example of Fibonacci Function.

What is Fibonacci Function?

Fibonacci function is defined as f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2) (Quite Simple)
For example
f(3) = f(3-1) + f(3-2)
f(3) = f(2) + f(1)
f(3) = f(2-1) + f(2-2) + f(1)
f(3) = f(1) + f(0) + f(1)
f(3) = 1 + 0 + 1
f(3) = 2

This is the way for calculating Fibonacci Function values in Mathematics. Let’s now look at How Fibonacci can be implemented in Python?

Implementing Fibonacci in Python?

Simplest approach in Python to implement Fibonacci will be to use Recursion. Below is Python code which implements Fibonacci Function.

def Fib(n):
	if n < 0:
		print("Incorrect input")

	elif n == 0:
		return 0

	elif n == 1 or n == 2:
		return 1

		return Fib(n-1) + Fib(n-2)

If calculated using Fib(n) function as described above Fib(2) = 1, Fib(4) = 3, Fib(5) = 5, Fib(6) = 8 and so on. But there is an issue with Fib(n) function here. Let's understand what that is?
Below are the steps which Python need to executed to compute value of Fib(5). So many steps.

Fib(5) = Fib(5-1) + Fib(5-2)
Fib(5) = Fib(4) + Fib(3)
Fib(5) = Fib(4-1) + Fib(4-2) + Fib(3-1) + Fib(3-2)
Fib(5) = Fib(3) + Fib(2) + Fib(2) + Fib(1)
Fib(5) = Fib(3) + 2 * Fib(2) + Fib(1)
Fib(5) = Fib(3-1) + Fib(3-2) + 2 *(Fib(2-1) + Fib(2-2)) + Fib(1)
Fib(5) = Fib(2) + Fib(1) + 2 * (Fib(1) + Fib(0)) + Fib(1)
Fib(5) = Fib(2-1) + Fib(2-2) + Fib(1) + 2 * (Fib(1) + Fib(0)) + Fib(1)
Fib(5) = Fib(1) + Fib(0) + Fib(1) + 2Fib(1) + 2Fib(0) + Fib(1)
Fib(5) = 5Fib(1) + 3Fib(0)
Fib(5) = 5 + 0 = 5 

As you can clearly see from above in order to compute Fib(5) Python need values of Fib(4), F(3) but in order to compute those it further needs values of Fib(2) and so on until it gets to Fib(1) or Fib(0).

Owing to this computing values again and again, it takes a lot of time. But what if Python already have value of Fib(4), Fib(3) while it's computing Fib(5). Then in just few steps value of Fib(5) will be calculated. Quite Simple.

Python code for calculating Fibonacci Function using Recursion

So having already computed values of Fib(4), Fib(3) makes it easier to compute value of Fib(5). Let's now see How this can be implemented in Python Code?

Memoized Fibonacci Function

Memoized Fibonacci Function stores values of Fib(x) so that values of Fib(y) can be computed quickly, here y > x.
Let's see Python Code for implement memorized Fibonacci function.

memo = {}

def Fib(n):
	if n in memo:
		return memo[n]

	if n == 0:
		memo[0] = 0
		return 0

	if n == 1:
		memo[1] = 1
		return 1

	val = Fib(n-1) + Fib(n-2)
	memo[n] = val
	return val

In this function before computing any value Fib(4) or some like this. Python would look for that value inside memo dictionary. If value is there access it and use it return memo[n] otherwise move forward and compute it. After computing it store it into memo for using later memo[n] = val.

Computing Fibonacci Numbers in Python using Memoization

Below is a graphical picture showing How Python uses Memoization for filling up dictionary memo to use these values later on.

Memoization in Python Programming Language

Now as Python already have values for Fib(3), Fib(2), Fib(4) inside memo dictionary so for next time to computer fib(6) python need to do less computation work. Let's calculate Fib(6).

Fib(6) = Fib(6-1) + Fib(6-2)
Fib(6) = Fib(5) + Fib(4)
Fib(6) = Fib(5-1) + Fib(5-2) + Fib(4)
Fib(6) = Fib(4) + Fib(3) + Fib(4)
Fib(6) = 3 + 2 + 3
Fib(6) = 8

Here in the above example - You can clearly see that Python doesn't need to compute values for Fib(4), Fib(3) it just need to access these values from memo dictionary.

This reduces time to compute Fib(6) value, that's why Memoization is quite helpful as it help to decrease time needed for doing computations.

Final Thoughts

Memoization is helpful for reducing time to do computations as Python doesn't need to compute same stuff again and again. This could also increase little bit speed of execution of Python Code, which is always great.
Not only for Fibonacci Function, Memoization can also be implemented for other well know Mathematical Functions like Permutations/Combinations.

If you have some question/suggestion about this article, please comment down and I would try to reply as soon as possible. Happy Coding 🥳

Comments to: Memoization in Python

Your email address will not be published.