6
\$\begingroup\$

I went ahead and implemented a method to calculate Fibonacci numbers using memoization.

public class MemoizedFibonacci {
    private static final List<BigInteger> FIBONACCI_LIST = new ArrayList<>();
    static {
        FIBONACCI_LIST.add(BigInteger.ZERO);
        FIBONACCI_LIST.add(BigInteger.ONE);
    }

    public static BigInteger fibonacci(final int number) {
        if (number < 0){
            throw new IllegalArgumentException("negative number: " + number);
        }
        if (isInFibonacciList(number)) {
            return FIBONACCI_LIST.get(number);
        }
        BigInteger fibonacci = fibonacci(number - 1).add(fibonacci(number - 2));
        FIBONACCI_LIST.add(fibonacci);
        return fibonacci;
    }

    private static boolean isInFibonacciList(final int number) {
        return (number <= FIBONACCI_LIST.size() - 1);
    }
}

I'd like feedback on all aspects of the code.

\$\endgroup\$
1
  • \$\begingroup\$ The recursive solution is slow, but easy to implement. You have given me an idea to simplify my own though. Thanks for posting this. \$\endgroup\$
    – RubberDuck
    Jul 13, 2014 at 20:08

1 Answer 1

8
\$\begingroup\$

This method is 'off':

private static boolean isInFibonacciList(final int number) {
    return (number <= FIBONACCI_LIST.size() - 1);
}

That should probably be:

private static boolean isInFibonacciList(final int number) {
    return number < FIBONACCI_LIST.size();
}

which begs the question as to why the function is needed at all. Just have number < FIBONACCI_LIST.size() in your code.

if (number < FIBONACCI_LIST.size()) {
    return FIBONACCI_LIST.get(number);
}

which is more readable than:

if (isInFibonacciList(number)) {
    return FIBONACCI_LIST.get(number);
}

....

private static boolean isInFibonacciList(final int number) {
    return (number <= FIBONACCI_LIST.size() - 1);
}

Finally, this class fails. Consider the use case:

public static void main(String[] args) {
    System.out.println(MemoizedFibonacci.fibonacci(10000));
}

This will attempt 10,000 levels of recursion, and will fail. Your class depends on the stack depth to determine whether an input value will succeed or not.

Recursion is not the right solution here, an iterative approach would be faster, and work in more cases.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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