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 non-linear 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 ofmemoization.

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(x-1) + fibonacci(x-2);
}

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 tofibonacci(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 linear-time 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 functionwould 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(n-1) + fibonacci(n-2));
}

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 tofibonacci(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(n-1),
fibonacci(n-2)));
}

This method would start failing for fibonacci(93). If we need to go over 92 we would have to useBigInteger 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.