# Recursive Fibonacci in Java

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;
}

• Just wanted to comment that the Fibonacci sequence is the classic "Obvious candidate for recursion but also sucks when you implement it recursively" algorithm. It's easy to see how recursion lends itself, but it's really much better implemented as a iterative format. Have you considered implementing binary search as another piece of practice? That is an algorithm that lends itself to recursion. Mar 28, 2018 at 19:19

Have you tried running this with a "big" input? Try it with fibonacci(10000) for example. At least on my machine with default settings this gives a StackOverflowError.

This is because java doesn't handle recursion well. Since you're going to recalculate all the values for each call to ´fibonacci(n) you might as well solve it with a simple for loop instead.

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;

int f1 = 0;
int f2 = 1;
for(int i = 2; i <= n; i++){
int temp = f2;
f2 += f1;
f1 = temp;
}
return f2;
}


It's not possible to change the return type dynamically based on a runtime value. Seeing how fibonacci numbers grow incredibly fast, you might want to consider returning BigInteger by default. (For ints, you can't even get to number 50).

public static BigInteger fibonacci(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative.");
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;

BigInteger f1 = BigInteger.ZERO;
BigInteger f2 = BigInteger.ONE;
for(int i = 2; i <= n; i++){
BigInteger temp = f2;
`