HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Memoized Fibonacci

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
memoizedfibonaccistackoverflow

Problem

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

public class MemoizedFibonacci {
    private static final List 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.

Solution

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.

Code Snippets

private static boolean isInFibonacciList(final int number) {
    return (number <= FIBONACCI_LIST.size() - 1);
}
private static boolean isInFibonacciList(final int number) {
    return number < FIBONACCI_LIST.size();
}
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);
}
public static void main(String[] args) {
    System.out.println(MemoizedFibonacci.fibonacci(10000));
}

Context

StackExchange Code Review Q#56940, answer score: 8

Revisions (0)

No revisions yet.