## Thursday, May 5, 2022

### Question 102 : What is Memoization.

Would you like to do same task again and again when you know that it is going to give you same result? I think Answer will be No.

So `Memoization` ensures that method does not execute more than once for same inputs by storing the results in the data structure(Usually `Hashtable` or HasMap  or `Array`).
Let’s understand with the help of Fibonacci example.

``0,1,1,2,3,5,8,13,21,34,55,89,144.``

So it has recurrence relation of:

``F(n)= F(n-1)+F(n-2)``

So Let’s write recurrence function for it.

`````` // Fibonacci without Memoization
public int fibonacci(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;

System.out.println("Calculating fibonacci number for: "+n);
return (fibonacci(n-1) + fibonacci(n-2));
}
``````

When you run above code with n=5, you will get below output.

``````Calculating fibonacci number for: 5
Calculating fibonacci number for: 4
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Calculating fibonacci number for: 2
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Fibonacci value for n=5: 5``````
As you can see, we are calculating fibonacci number for 2 and 3 more than once.
Let’s draw a `recursive tree` for fibonacci series with n=5.
Here two children of node will represent recursive call it makes.

If you notice here, we are calculating `f(3)` twice and `f(2)` thrice here, we can avoid duplication with the helping of caching the results.
We will use one instance variable memoizeTable for caching the result.

• Check if `n` is already present in `memoizeTable`, if yes, return the value
• If `n` is not present in `memoizeTable`, then compute and put the result in `memoizeTable`.
``````import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoizationAlgorithm {

private Map<Integer, Integer> memoizeTable = new HashMap<>(); // O(1)

// Fibonacci with Memoization
public int fibonacciMemoize(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;

if( this.memoizeTable.containsKey(n) )
{
System.out.println("Getting value from computed result for "+n);
return this.memoizeTable.get(n);
}

int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);

System.out.println("Putting result in cache for "+n);
this.memoizeTable.put(n, result);

return result;

}

// Fibonacci without Memoization
public int fibonacci(int n){

if( n == 0 ) return 0;
if( n == 1 ) return 1;

System.out.println("Calculating fibonacci number for: "+n);
return (fibonacci(n-1) + fibonacci(n-2));
}

public static void main(String[] args) {

FibonacciMemoizationAlgorithm fibonacciAlgorithm = new FibonacciMemoizationAlgorithm();
System.out.println("Fibonacci value for n=5:  "+fibonacciAlgorithm.fibonacciMemoize(5));

}
}
``````

When you run above program, you will get below output.

``````Putting result in cache for 2
Putting result in cache for 3
Getting value from computed result for 2
Putting result in cache for 4
Getting value from computed result for 3
Putting result in cache for 5
Fibonacci value for n=5: 5``````

As you can see, we are not computing fibonacci number for 2 and 3 more than once.

That’s all about `Memoization` in java.

## You may also like

a
Kubernetes AWS Java Coding Question
Microservices Core Java Python
Spring Framework AI/MLSpring Boot