## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# Memoization

## Memoization

Memoization is a technique where results are stored to avoid doing the same computations many times.

When Memoization is used to improve recursive algorithms, it is called a "top-down" approach because of how it starts with the main problem and breaks it down into smaller subproblems.

Memoization is used in Dynamic Programming.

## Using Memoization To Find The $$n$$th Fibonacci Number

The $$n$$th Fibonacci number can be found using recursion. Read more about how that is done on this page.

The problem with this implementation is that the number of computations and recursive calls "explodes" when trying to find a higher Fibonacci number, because the same computations are done over and over again.

### Example

Find the 6th Fibonacci number with recursion:

def F(n):
print('Computing F('+str(n)+')')
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)

print('F(6) = ',F(6))
Run Example »

As you can see from running the example above, there are 25 computations, with the same computations done many times, even for just finding the 6th Fibonacci number.

But using memoization can help finding the $$n$$th Fibonacci number using recursion much more effectively.

We use memoization by creating an array memo to hold the Fibonacci numbers, so that Fibonacci number n can be found as element memo[n]. And we only compute the Fibonacci number if it does not already exist in the memo array.

### Example

Find the 6th Fibonacci number with recursion, but using memoization to avoid unnecessary recursive calls:

def F(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
print('Computing F('+str(n)+')')
if n <= 1:
memo[n] = n
else:
memo[n] = F(n - 1) + F(n - 2)
return memo[n]

memo = [None]*7
print('F(6) = ',F(6))
print('memo = ',memo)
Run Example »

As you can see by running the examples above, memoization is very helpful to reduce the number of computations.

The number of computations is reduced from 25 in the initial code, to just 7 in the last example using memoization, and the benefit of using memoization increases really fast by how high the Fibonacci number we want to find is.

Finding the 30th Fibonacci number requires 2,692,537 computations in the initial code, but it just requires 31 computations in the algorithm implemented using memoization!

You get this result by running the code below.

### Example

See the difference in calculations for finding the 30th Fibonacci number, with and without memoization:

computation_count = 0
def F(n):
global computation_count
computation_count += 1
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)

computation_count_mem = 0
def F_mem(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
global computation_count_mem
computation_count_mem += 1
if n <= 1:
memo[n] = n
else:
memo[n] = F_mem(n - 1) + F_mem(n - 2)
return memo[n]

print('F(30) = ',F(30))
print(f'Number of computations: {computation_count}')
print('\nUsing memoization:')
memo = [None]*31
print('F(30) = ',F_mem(30))
print(f'Number of computations with memoiztion: {computation_count_mem}')
Run Example »

## Memoization in AVL Trees

An AVL tree is a type of Binary Tree that is self-balancing.

Every time a node is inserted or deleted from an AVL tree, the balancing factor must be calculated for all ancestors, using the height of the left and right subtrees to find out if a rotation is needed to restore balance.

To avoid calculating the height of each node (going all the way down to the leaf nodes) to calculate the balancing factors, each node has its subtree height stored.

### Example

class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
Run Example »

This means that to find the balance factor for a node, the already stored left child's height is subtracted from the already stored right child's height, no other calculations needed.

Storing height in AVL trees is a form of memoization, because values are stored to avoid re-calculating them. In AVL trees, when the height is stored like this, it is called an augmented property.

An augmented property is a property of an element that does not have to be stored, but is stored to make operations more efficient.

The node heights must be calculated at some point of course, but that is only done when strictly needed, using retracing.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com