##### 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:

, with seed values ,

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import java.math.BigInteger; public class FibonacciSlow { public static BigInteger fib(int N) { if (N == 0) return BigInteger.ZERO; if (N == 1) return BigInteger.ONE; return fib(N-1).add(fib(N-2)); } public static void main(String[] args) { // print first 100 Fibonacci numbers for(int N = 0; N < 100; N++) System.out.println(N + " " + fib(N)); } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import java.math.BigInteger; public class Fibonacci { private static BigInteger[] values = new BigInteger[100]; public static BigInteger fib(int N) { if (N == 0) { values[0] = BigInteger.ZERO; return values[0]; } else if (N == 1) { values[1] = BigInteger.ONE; return values[1]; } else { values[N] = values[N-2].add(values[N-1]); } return fib(N-1).add(values[N-2]); } public static void main(String[] args) { // print first 100 Fibonacci numbers for(int N = 0; N < 100; N++) System.out.println(N + " " + fib(N)); } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 11 89 12 144 13 233 14 377 15 610 16 987 17 1597 18 2584 19 4181 20 6765 21 10946 22 17711 23 28657 24 46368 25 75025 26 121393 27 196418 28 317811 29 514229 30 832040 31 1346269 32 2178309 33 3524578 34 5702887 35 9227465 36 14930352 37 24157817 38 39088169 39 63245986 40 102334155 41 165580141 42 267914296 43 433494437 44 701408733 45 1134903170 46 1836311903 47 2971215073 48 4807526976 49 7778742049 50 12586269025 51 20365011074 52 32951280099 53 53316291173 54 86267571272 55 139583862445 56 225851433717 57 365435296162 58 591286729879 59 956722026041 60 1548008755920 61 2504730781961 62 4052739537881 63 6557470319842 64 10610209857723 65 17167680177565 66 27777890035288 67 44945570212853 68 72723460248141 69 117669030460994 70 190392490709135 71 308061521170129 72 498454011879264 73 806515533049393 74 1304969544928657 75 2111485077978050 76 3416454622906707 77 5527939700884757 78 8944394323791464 79 14472334024676221 80 23416728348467685 81 37889062373143906 82 61305790721611591 83 99194853094755497 84 160500643816367088 85 259695496911122585 86 420196140727489673 87 679891637638612258 88 1100087778366101931 89 1779979416004714189 90 2880067194370816120 91 4660046610375530309 92 7540113804746346429 93 12200160415121876738 94 19740274219868223167 95 31940434634990099905 96 51680708854858323072 97 83621143489848422977 98 135301852344706746049 99 218922995834555169026 |