patternjavaMinor
Memoized Fibonacci
Viewed 0 times
memoizedfibonaccistackoverflow
Problem
I went ahead and implemented a method to calculate Fibonacci numbers using memoization.
I'd like feedback on all aspects of the code.
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':
That should probably be:
which begs the question as to why the function is needed at all. Just have
which is more readable than:
Finally, this class fails. Consider the use case:
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.
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.