In class we have written two programs to compute an element of the Fibonacci sequence, one using a loop (iteration) and one using recursion. If you compile and run both programs, you may notice that the one using recursion can be quite slow with all but small inputs. The reason for that is fairly obvious if you think about how it works -- the recursive function does quite a lot of duplicate computation. One way to improve the performance of such a function is with a technique referred to as memoization2, in which every time you compute a result you save it for possible reuse. Because I was curious myself about how the iterative and recursive versions compared, and how much memoization might help, I wrote a program that defines functions for all three approaches (using long long rather than long for the elements of the sequence, to allow computing larger values) and times them. For me only the simple recursive function took more than trivial time, so I added code to also count the number of recursive calls. You can find the result -- minus the actual computation of values! -- in fibonacci-starter.c. Sample output for an input of 46: 

which index? computing fibonacci(46) iterative version: result 2971215073 (time 0.00000000) recursive version: result 2971215073 (time 46.40543509, count 5942430145) memoized recursive version: result 2971215073 (time 0.00000095, count 91) 

Your mission is to fill in the blanks in this starter program so that it performs the desired computation. (Look for comments with the word FIXME.) For the iterative and simple recursive approaches, you can get the code from the course ``sample programs'' page; you will just need to change some data types from int to long long.

For the memoized recursive approach, a simple way to use this technique is to have an array for saving previously-computed results, with the n-th element of the Fibonacci sequence stored as the n-th element of the array, and a value of 0 meaning ``has not been previously computed''. This array could be an additional argument for the function, or it could be a global variable. (Usually global variables are discouraged, but for this problem they might make sense.) If you take the global-variable approach, your program should do something reasonable if it isn't big enough, perhaps just rejecting any input that would overflow it.

The only changes you should need to make in the starter program are:

Fill in the body of functions fibonacci_iterate() and fibonacci_recurse(). It's okay to use code from the ``sample programs'' page (edited so it computes a long long), and in fact that is what I strongly recommend. (I didn't just do this for you myself because I hope that copying and pasting will encourage you to look at the copied/pasted code.)

Fill in the body of function fibonacci_recurse_m(). You can add additional parameters if you like, or use global variables for the saved values.

Turn in the resulting code. Note that all three functions should return the same value for the n-th element of the Fibonacci sequence; the only difference should be execution time and count of recursive calls. I'm not asking you (at this point?) to formally collect results that would show how the count of recursive calls, and the execution time, increases as the input variable increases, but you may find it interesting to try some different values and observe!

 /* * Program to compare performance of various ways of computing * an element of the Fibonacci sequence: iterative, recursive, * and recursive with memoization. */ #include  #include  #include  /* for get_time */ double get_time(); long long fibonacci_iterate(int n); long long fibonacci_recurse(int n, long long *count); long long fibonacci_recurse_m(int n, long long *count); int main(void) { int n; printf("which index? "); if ((scanf("%d", &n) != 1) || (n < 0)) { printf("input must be a non-negative integer "); return 1; } double start_time, end_time; long long result; long long count; printf("computing fibonacci(%d) ", n); start_time = get_time(); result = fibonacci_iterate(n); end_time = get_time(); puts(" iterative version:"); printf("result %lld (time %.8f seconds) ", result, end_time - start_time); start_time = get_time(); count = 0; result = fibonacci_recurse(n, &count); end_time = get_time(); puts(" recursive version:"); printf("result %lld (time %.8f seconds, count %lld) ", result, end_time - start_time, count); start_time = get_time(); count = 0; result = fibonacci_recurse_m(n, &count); end_time = get_time(); puts(" memoized recursive version:"); printf("result %lld (time %.8f seconds, count %lld) ", result, end_time - start_time, count); return 0; } /* * compute the n-th fibonacci number using iteration */ long long fibonacci_iterate(int n) { /* * FIXME add code here * * okay to use code from sample program -- that is what I recommend -- * but remember you are computing a "long long" not a "long". */ return 0; /* to make the compiler happy for now */ } /* * compute the n-th fibonacci number using recursion (naive version) */ long long fibonacci_recurse(int n, long long *count) { (*count)+=1; /* * FIXME add code here * * okay to use code from sample program -- that is what I recommend -- * but remember you are computing a "long long" not a "long". */ return 0; /* to make the compiler happy for now */ } /* * compute the n-th fibonacci number using recursion (version using * memoization) */ long long fibonacci_recurse_m(int n, long long *count) { (*count)+=1; /* * FIXME add code here * * this is the only function you can't just copy-and-paste. * again remember that you are computing a "long long" so saved * values should be of that type. */ return 0; /* to make the compiler happy for now */ } /* * get time in seconds since "epoch" * uses Linux library function gettimeofday, so probably not portable */ double get_time() { struct timeval tv; if (gettimeofday(&tv, NULL) == 0) return (double) tv.tv_sec + ((double) tv.tv_usec / (double) 1000000); else return 0.0; }