Memoized Fibonacci Numbers with Java 8
Join the DZone community and get the full member experience.
Join For Free
since today is fibonacci day , i decided that it would be interesting to publish something related to it.
i believe one of the first algorithms we all see when learning nonlinear recursion is that of calculating a fibonacci number. i found a great explanation on the subject in the book
structure and interpretation of computer programs
[sic] and i dedicated some time to playing with the fibonacci algorithm just for fun. while doing so i found an interesting way to improve the classical recursive algorithm by using one of the new methods (added in java 8) in the
map
interface and which i used here to implement a form of
memoization
.
classical recursive fibonacci
in the classical definition of fibonacci we learn that:
we program this very easily in java:
public static long fibonacci(int x) { if(x==0  x==1) return x; return fibonacci(x1) + fibonacci(x2); }
now the problem with this algorithm is that, with the exception of the base case, we recursively invoke our function twice and interestingly one of the branches recalculates part of other branch every time we invoke the function. consider the following image (taken from sic) that represents an invocation to
fibonacci(5)
.
clearly the branch to the right is redoing all the work already done during the recursive process carried out by the left branch. can you see how many times
fibonacci(2)
was calculated? the problem gets worse as the function argument gets bigger. in fact this problem is so serious that the calculation of a small argument like
fibonacci(50)
might take quite a long time.
memoized recursive fibonacci
however, there is a way to improve the performance of the original recursive algorithm (i mean without having to resort to a lineartime algorithm using, for instance, binet’s formula ).
the serious problem we have in the original algorithm is that we do too much rework. so, we could alleviate the problem by using memoization , in other words by providing a mechanism to avoid repeated calculations by caching results in a lookup table that can later be used to retrieve the values of already processed arguments.
in java we could try to store the fibonacci numbers in a hast table or map. in the case of the left branch we’ll have to run the entire recursive process to obtain the corresponding fibonacci sequence values, but as we find them, we update the hash table with the results obtained. this way, the right branches will only perform a table lookup and the corresponding value will be retrieved from the hash table and not through a recursive calculation again.
some of the new methods in the class map , in java 8, simplify a lot the writing of such algorithm, particularly the method
computeifabsent(key, function)
. where the
key
would be the number for which we would like to look up the corresponding fibonacci number and the
function
would be a lambda expression capable of triggering the recursive calculation if the corresponding value is not already present in the map.
so, we can start by defining a map and putting the values in it for the base cases, namely,
fibonnaci(0)
and
fibonacci(1)
:
private static map<integer,long> memo = new hashmap<>(); static { memo.put(0,0l); //fibonacci(0) memo.put(1,1l); //fibonacci(1) }

and for the inductive step all we have to do is redefine our fibonacci function as follows:
public static long fibonacci(int x) { return memo.computeifabsent(x, n > fibonacci(n1) + fibonacci(n2)); }
as you can see, the method
computeifabsent
will use the provided lambda expression to calculate the fibonacci number when the number is not present in the map, this recursive process will be triggered entirely for the left branch, but the right branch will use the momoized values. this represents a significant improvement.
based on my subjective observation, this improved recursive version was outstandingly faster for a discrete number like
fibonacci(70)
. with this algorithm we can safely calculate up to
fibonacci(92)
without running into
long
overflow. even better, to be sure that our algorithm would never cause overflows without letting the user know we could also use one of the new methods in java 8 added to the
math
class and which throws an
arithmeticexception
when overflow occurs. so we could change our code as follows:
public static long fibonacci(int x) { return memo.computeifabsent(x, n > math.addexact(fibonacci(n1), fibonacci(n2))); }
this method would start failing for
fibonacci(93)
. if we need to go over 92 we would have to use
biginteger
in our algorithm, instead of just long.
notice that the memozied example uses mutations, therefore, in order to use this code in a multithreaded environment we would first need to add some form of synchronization to the proposed code, or use a different map implementation, perhaps a
concurrenthashmap
, which evidently, may impact performance as well. arguably, this would still be better than the original recursive algorithm.
Published at DZone with permission of Edwin Dalorzo. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments