/ Published in: Java
Demonstrates just how bad the recursive Fibonacci performs without memoization and what difference memoization makes.
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
import java.util.Arrays; public class FibonacciMemoize { private static abstract class Fibber { long opCount; void reset() { opCount = 0; } abstract int fib(final int source); } private static class FibberBrute extends Fibber { @Override public int fib(int n) { opCount++; return n < 2 ? n : fib(n - 1) + fib(n - 2); } } private static class FibberMemo extends Fibber { private int memo[] = new int[1024]; @Override void reset() { super.reset(); } @Override public int fib(int n) { opCount++; int retVal = n < 2 ? n : ( memo[n] == 0 ? fib(n - 1) + fib(n - 2) : memo[n]); memo[n] = retVal; return retVal; } } final Fibber[] fibbers = { new FibberBrute(), new FibberMemo()}; for(int i = 0; i <= max; i++) { for(final Fibber fibber: fibbers) { fibber.reset(); final int result = fibber.fib(i); check = result; } + "\" returned result " + result + " while previous result was " + check + " for n=" + i); } } } }