What is Memoization

Learn about Memoization and how to implement it.

Memoization is a software optimization technique used to speed up programs. It increases the performance of a function by caching its output based on its input.

Let’s say we have to implement a function that creates a Fibonacci sequence.

The Fibonacci sequence looks like this [1,1,2,3,5,8,13,21]. To create a Fibonacci sequence, we can implement recursion.

Recursion is a function that calls itself. It is used when a problem can be solved by dividing it into smaller problems, these smaller problems can use the same algorithm to be solved.

def fib(n):
    if n <= 2:
       return 1
    else:
       return fib(n-1) + fib(n-2)

    print(fib(4))

If we want to calculate the Fibonacci of 4, we would get 3. If we were to calculate a larger number like 100, the function would take a longer time to run before it returns the result.

To optimize this solution, we can make use of a Cache. To implement the cache, we create a dictionary called nums that stores n as the key and the result of fib_top_down(n) as the value. This makes our function run faster because it does not have to calculate the same values over and over again.

nums = {}

def fib_memo(n):
    if n <= 2:
       return 1
    if n in nums:
       return nums[n]
    else:
       num = fib_memo(n-1) + fib_memo(n-2)
       nums[n] = num
       return num

---

Memoization is used in ReactJS to save computes by skipping redundant function calls within a React component. You can read more about this here: useMemo

Thank you for reading. Kindly subscribe to get more Computer Science tips.