Fibonacci numbers are defined as F(1)=1, F(2)=1, F(i) = F(i-1)+F(i-2), i=2,

Write a C program, named fibonacci.h, containing the following two functions.

1- int recursive_fibonacci(int n) which computes and returns the nth Fibonacci number F(n) using recursive algorithm (i.e., using recursive function).

2- int iterative_fibonacci(int n) which computes and returns the nth Fibonacci number F(n) using iterative algorithm (i.e., using a loop).

Add a global pointer to the above functions to hold the lowest memory address of the local variables in call stack.

Use the provided the main function program fibonacci_main.c to compare the space and time usages of the two functions. The output should be like the following. Note that values iterative_fibonacci(40) and recursive_fibonacci(40) should be the same as in the public test. Address and time span values will be different.

Read and understand how the global pointers are used to measure the memory spans in call iterative_fibonacci(40) and iterative_fibonacci(40) and recursive_fibonacci(40), and how the running time spans are measured and compared.

Public test

command: gcc fibonacci_main.c -o fibonacci command: fibonacci 40 iterative_fibonacci(40):102334155 recursive_fibonacci(40):102334155 command: fibonacci **Iterative algorithm measurement** iterative_fibonacci(40):102334155 high address:6422260 low address:6422208 iterative_fibonacci(40) memory span:52 time_span(iterative_fibonacci(40) for 500000 times):86.0 (ms) **Recursive algorithm measurement** recursive_fibonacci(40):102334155 high address:6422260 low address:6420992 recursive_fibonacci(40) memory span:1268 time_span(recursive_fibonacci(40) for 10 times) in (ms):10789.0 **Comparison of recursive and iterative algorithms** memory_span(recursive_fibonacci(40))/memory_span(iterative_fibonacci(40)):24.4 time_span(recursive_fibonacci(40))/time_span(iterative_fibonacci(40)):6272674.4 

fibonacci_main.c:

*/ #include #include #include "fibonacci.h"

int *la; int *ha;

int main(int argc, char *argv[]){ int i=0, n = 40; clock_t t1, t2; if (argc > 1 ) { sscanf(argv[1], "%d", &n); printf("iterative_fibonacci(%d):%d ", n, iterative_fibonacci(n)); printf("recursive_fibonacci(%d):%d ", n, recursive_fibonacci(n)); } else {

printf("**Iterative algorithm measurement** "); ha = &i; la = ha; printf("iterative_fibonacci(%d):%d ", n, iterative_fibonacci(n)); printf("high address:%lu ", ha); printf("low address:%lu ", la); int memory_span1 = (unsigned long) ha - (unsigned long) la; printf("iterative_fibonacci(%d) memory span:%d ", n, memory_span1);

//run time measuring for iterative_fibonacci int m1 = 500000; t1=clock(); for (i=0; i< m1; i++) { iterative_fibonacci(n); } t2=clock(); double time_span1 = (double) t2-t1; printf("time_span(iterative_fibonacci(%d) for %d times):%0.1f (ms) ", n, m1, time_span1); printf(" **Recursive algorithm measurement** "); la = ha; printf("recursive_fibonacci(%d):%d ", n, recursive_fibonacci(n)); printf("high address:%lu ", ha); printf("low address:%lu ", la); int memory_span2 = (unsigned long) ha - (unsigned long) la; printf("recursive_fibonacci(%d) memory span:%d ", n, memory_span2); //run time measuring recursive_fibonacci int m2 = 10; t1=clock(); for (i=0; i

fibonacci.h:

/* * your program signature */ #ifndef FIBONACCI_H #define FIBONACCI_H extern int *la; // global pointer variable to hold lowest variable address int recursive_fibonacci(int n) { if (&n < la) la = &n; // your implementation of the recursive algorithm } int iterative_fibonacci(int n) { if (&n < la) la = &n; // your implementation of the iterative algorithm } #endif