Recursive Fibonacci memoization
I believe you forget to actually look up stuff in your dictionary.
Change
else
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);
to
else {
if (dictionary[n] > 0)
return dictionary[n];
return dictionary[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
and it works just fine (tested it myself :)
public static int fib(int n, Map<Integer,Integer> map){
if(n ==0){
return 0;
}
if(n ==1){
return 1;
}
if(map.containsKey(n)){
return map.get(n);
}
Integer fibForN = fib(n-1,map) + fib(n-2,map);
map.put(n, fibForN);
return fibForN;
}
Similar to most solutions above but using a Map instead.
You need to distinguish between already calculated number and not calculated numbers in the dictionary, which you currently don't: you always recalculate the numbers.
if (n == 0)
{
// special case because fib(0) is 0
return dictionary[0];
}
else
{
int f = dictionary[n];
if (f == 0) {
// number wasn't calculated yet.
f = fibonacci(n-1) + fibonacci(n-2);
dictionary[n] = f;
}
return f;
}
Program to print first n
fibonacci numbers using Memoization.
int[] dictionary;
// Get Fibonacci with Memoization
public int getFibWithMem(int n) {
if (dictionary == null) {
dictionary = new int[n];
}
if (dictionary[n - 1] == 0) {
if (n <= 2) {
dictionary[n - 1] = n - 1;
} else {
dictionary[n - 1] = getFibWithMem(n - 1) + getFibWithMem(n - 2);
}
}
return dictionary[n - 1];
}
public void printFibonacci()
{
for (int curr : dictionary) {
System.out.print("F[" + i++ + "]:" + curr + ", ");
}
}