1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Adonalsium Mar 28 '18 at 19:19
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.