Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I went ahead and I 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.

share|improve this question
    
The recursive solution is slow, but easy to implement. You have given me an idea to simplify my own though. Thanks for posting this. –  ckuhn203 Jul 13 at 20:08

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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