Recursive Fibonacci in Java

Question

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

Answer 1

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;
        f2 = f2.add(f1);
        f1 = temp;
    }
    return f2;
}

Personally I would also not memoize fibonacci numbers further than these 2 temp veriables to keep track of the last 2 values. If your program is intended to request fibonacci numbers over and over and you're willing to get a little bit of speed in exchange for some memory you could also precompute a lot of those numbers. Except for learning purposes I don't think it's actually worth doing though.