As discussed in class, the classic, recursive implementation of the computation of the n fibonacci number is horribly slow. Here is an example of this implementation: Fibonacci.java. Here is some output I got from running this program; the 10th, 20th, and 30th Fibonacci numbers are easily computed, but the 40th Fibonacci number takes 770 milliseconds, and the 50th took 94276 milliseconds (more than a minute). I was unable to get fibonacci(60) to terminate with 15-20 minutes!

The 10th Fibonacci number is 55
It took 0 milliseconds to compute it.
The 20th Fibonacci number is 6765
It took 2 milliseconds to compute it.
The 30th Fibonacci number is 832040
It took 10 milliseconds to compute it.
The 40th Fibonacci number is 102334155
It took 770 milliseconds to compute it.
The 50th Fibonacci number is -298632863
It took 94276 milliseconds to compute it.

It is more interesting to try and deal with the explosion in running time. An easy (but, somewhat uninteresting) fix is to get rid of recursion entirely and just use a simple iterative algorithm that uses 2-3 variables to keep track of the last two elements of the fibonacci sequence. A more interesting approach is to keep the recursion more or less intact, but speed it up greatly by observing that

• the slowness of the standard, recursive implementation of fibonacci numbers is due to the same computation being repeated many many times, and
• these multiple, identical computations can be avoided by remembering old answers in a table.

Problem. Implement a "fast" version of a recursive fibonacci number computation. To compute the nth Fibonacci number define an array of answers of size n. The idea is that the value of the kth Fibonacci number will be stored in slot k-1, as soon as it is computed the very first time. Subsequently, whenever fibonacci(k) is needed a constant time table lookup will suffice. The answers table is initialized to 0; in general, 0 in a slot indicates that the corresponding answer has not yet been computed. Using the fast, recursive fibonacci function, compute the 500th Fibonacci number.