A Look at the Fibonacci Numbers using Java

Fibonacci: Its Origins

The Fibonacci numbers or sequence which I want to discuss today has been around for a long time and according to Wikipedia its origins may date back to as far back as 200 BC with Pingala. It was later associated with others such as Virahanka (c. 700 AD), Gopāla (c. 1135), and Hemachandra (c. 1150).  However, in the West, the Fibonacci sequence is most readily associated with Leonardo Pisano Bigollo (c. 1170 – c. 1250).  He is also known more famously as Leonardo of Pisa but other forms of his name include Leonardo Pisano, Leonardo Bonacci, or Leonardo Fibonacci. 

Over the years the years this sequence has been studied mathematically and it has been discovered in real life in nature.  More specifically, in biological settings it has been found in such things as branching in trees, arrangement of leaves on a stem, the fruitlets of a pineapple, the flowering of artichoke, an uncurling fern, the arrangement of a pine cone,and also in the family tree of honeybees.

Mathematically the Fibonacci sequence is described by the following integer sequence:

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

It is represented by the following recurrence relation:

F_n = F_{n-1} + F_{n-2} , with seed values F_0 = 0 , F_1 = 1

Leonardo of Pisa wrote about this Fibonacci sequence in the thirteenth century in his book Liber Abaci in relation to the growth of rabbits.  He postulated having two rabbits (one of each sex) on an island and they would be allowed to breed.  He further stated that the pair of rabbits does not breed until they are two months old. But after they are two months old, each pair of rabbits produces another pair each month.  By studying this problem and process he derived the above Fibonacci sequence shown above.

With that bit of introduction out of the way I thought it would be fun to code up the Fibonacci sequence in Java.  The technique I will be using is recursion as it lends itself nicely to solving the Fibonacci sequence on a computer. I want to code up two different java versions of solving the fibonacci sequence to highlight the importance of choosing a good algorithm in solving a problem.  I will demonstrate this idea by creating a java program to print the first 100 fibonacci numbers in the sequence.  As you will come to see it’s not always the case that the most obvious way to solve a problem will provide the most efficient algorithm for larger problem sizes.

A Simple Recursive Slow Algorithm To Solve For Fibonacci

The first program I will show is the most natural way to solve for the Fibonacci sequence but it is also not the most efficient algorithm.  It will take a very long time for it to calculate and print the first 100 terms in the Fibonacci sequence.  In coding up the following program I make use of  java’s BigInteger class because I want to make sure that I can handle the big integers that the program produces as it reaches the 100th term.  If you are unaware of this class or haven’t used it before here is the API for it and a tutorial for you to learn about it.

As you can see above the fib function is a very simple recursive method.  It has two base cases  and two recursive calls to fib.  However, when  you run this program you will find that it takes quite some time to print out the first 100 terms of the Fibonacci sequence because the two recursive function calls are expensive and recalculates the same things over again.  Consequently, although the algorithm is elegant and works well for printing out the first few sequence numbers it becomes slow because of the repeated function calls.  This is algorithm can be improved through the use of memoization.

 A Faster Algorithm

With the two recursive function calls from the program above there is duplication and unnecessary recalculation of results that causes the program to be inefficient and slow as you try and solver for larger instances.  However, there is a way to improve the working of the program above by introducting memoization.  Memoization is an optimization technique used primarily to speed up computer programs by keeping the results of expensive function calls and returning the cached result when the same inputs occur again. this inefficiency.  An easy way to speed up the algorithm is to save the results of previous function call computations in an array and look them up as required instead of computing them.  This is what the following java program does.

As you can see the program is a bit more complicated but the benefits are enormous and immediately evident when you run the program.   One can now calculate larger instances of the fibonacci sequence in a reasonable amount of time.   Here is the list the above program produced and you can see they agree with the list available on the web here.