Problem

When computing a Fibonacci number using the most straightforward recursive function definition, the recursive solution recomputes each Fibonacci number too many times. To compute Fi+2 = Fi + Fi+1, it computes all the numbers computed in Fi a second time in computing Fi+1. You can avoid this by saving the numbers in an array while computing Fi. Write another version of your recursive Fibonacci function based on this idea. In the recursive solution for calculating the Nth Fibonacci number, declare an array of size N. Array entry with index i stores the ith (i ≤ N) Fibonacci number as it is computed the first time. Then use the array to avoid the second (redundant) recalculation of the Fibonacci numbers. Time this solution as in Programming Project 6, and compare it to your results for the iterative solution.