# Memoized Fibonacci

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

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));
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.

-
The recursive solution is slow, but easy to implement. You have given me an idea to simplify my own though. Thanks for posting this. – RubberDuck Jul 13 '14 at 20:08

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


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.

-