Memoization - Please dont ask to me to compute same values

Recently I was having conversation with my Delly,and Delly was really mad at me because she thinks I ask her to do the same things again and again.Here is the conversation between us

Delly       : Hey user101...!!!
user101   : Hi Delly, wassup ..??
Delly       : I am sorry user101, but if you are going to use me like this then i am afraid i am gonna have to stop running your codes.
user101   : What happen..wats wrong..???
Delly       : Whenever you write recursive code ,you ask me to do same computations again and again, Its boring and I really hate it.And you also ask JVM (Java Virtual Machine) to increase stack size and heap space.
Delly       : They make fun of you.JVM thinks you are bad programmer when it comes to recursive technique.They want you to use iterative approach so that they dont have to extend their memory.
Delly       : So i dont want you to use me. :(
user101   : Ohhh..!! i see.
user101   : Sorry delly but this is what i have learned during my academics.And all my friends use the same recursive technique.i dont know how i can make it efficient and avoid your rework.
Delly       : There is a technique called Memoization,you can use that....
user101   : ohk...let me check it on wiki..
(after 5 min.....)
user101   : Wow...!!! this is cool.Thanks Delly I will write about this technique on my blog...bye for now
Delly       : You are my programmer....love you...bye...

Well guys as i promised to Delly I am sharing my knowledge on Memoization with you...

Give me product of 3 * 4  ??
its 12 we all know

Now please give me product of 3 * 4 * 5
60..? right

How did you compute that...?
You must have used result of 3 * 4 which is 12 and then multiplied it with 5,which gives us the answer 60

You guys are smart..my Delly isnt..?? (sssshhhhh)
she recomputes 3 * 4 again and then result of (3 * 4) * 5
Now i see why she is so mad at me.

Whenever we write recursive programs e.g factorial,fibonnacci we ask computer to do computations which are already done before.
Here is code of simple recursive factorial program :

public class SimplyRecursive {

public static void main(String... args) {
System.out.println(new SimplyRecursive().fact(5));
System.out.println(new SimplyRecursive().fact(3));
}

public int fact(int n) {
if(n==0) return 1;
return(n * fact(n-1));
}
}

Now what above program does

fact(5)  = 5 * 4 * 3 * 2 * 1 * 0 = 120
fact(3)  = 3 * 2 * 1 * 1 * 0 = 6

Did you notice that for fact(3) we would have the answer if we would have saved our previous computations.

This technique of saving previously computed values is called MEMOIZATION.

I tried to implement this technique.It looked easy while reading but i had to put some serious efforts to make my code run using Memoization.The toughest part was how to save values,because in recursive approach all values are on stack and computed in descending order. So i don't have itermediate result in my hand to save.After scratching head for few hours i realized i should store values of compuation in recursion only.

Here is my modified code.

import java.util.HashMap;


public class Factorial_Memo {

private static HashMap<Integer,Integer>  map = new HashMap<Integer, Integer>();

public static void main(String[] args) throws Exception {
System.out.println(fact(4));
System.out.println(fact(8));
System.out.println(fact(6));
}

private static int fact(int n) {
if(n == 0) return 1;
if(map.containsKey(n)) return map.get(n);
int y = n * fact(n - 1);
map.put(n, y);
return y;
}
}

The key here is storing values in HashMap

int y = n * fact(n - 1);
map.put(n, y);

The above two statements will be executed only if value if not present in HashMap.This is how Memoization works.

If your are not java programmer,you don't get HashMap by default.Instead of writing code for creating HashMap you can use boolean and int array to store computed values.Make index of boolean array true while storing values.While reading,check if index value is true use index value of int array else compute value ,make index of boolean true and store value in an int array.

**Secret :
My Delly still dislikes many of my codes...she doesnt say anything but I can understand her.But she was really very happy when I did my Factorial_Memo.

Bye
Its time to get back to my Delly.