I just started learning recursion and memoization, so I decided to give a simple implementation a shot. Works with some simple test cases I came up with. Is there anything I can add to make this more interesting? I'm not sure if I can update the return type with generics somehow depending on the input "n" for long, BigInteger, etc.
public static int fibonacci(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative.");
if (n == 0) return 0;
if (n == 1) return 1;
// if n >= 2
Map<Integer, Integer> hm = new HashMap<Integer, Integer>(); // cache
hm.put(0, 0);
hm.put(1, 1);
return fibHelper(n-1, hm) + fibHelper(n-2, hm);
}
static int fibHelper(int n, Map<Integer, Integer> hm) {
if (hm.containsKey(n)) return hm.get(n);
int fn = fibHelper(n-1, hm) + fibHelper(n-2, hm); // fn = fib of n
hm.put(n, fn);
return fn;
}