The fibonacci sequence is a famous recursively built sequence. It is defined as:

The two base cases:

fib$(1)=1$

fib$(2)=1$

And the recursive formula:

fib$($n$)=$ fib$($n$-1)+$ fib$($n$-2)$

Example: fib$(5)=$ fib$(4)+$ fib$(3)=($fib$(3)+$ fib$(2))+($fib$(2)+$ fib$(1))=$

$($fib$(2)+$fib$(1)+1)+(1+1)=3+2=5.$

In C:

int fib$($int n$)$

$\{$

if $($n $==1||$ n $==2)$

return $1$;

else

return $($fib$($n$-2)+$ fib$($n$-1))$;

$\}$

Assignment: Write a program that uses the recursive Fibonacci function using the clock$()$

function, in C$/$C$++,$ to compute the time it takes to run the program. Run a number of

simulations $($run the program$)$ of this program and record the times to takes to compute various

Fibonacci numbers. You could enter your results in a table and$/$or graph and discuss the

results. If you use any references $($and perhaps you should$),$ you must list them in the

bibliography $($or references$).$

Your written work should have an introduction $($an abstract of what you want to show or what

you conjecture is true$)$; then the results and then a conclusion. In the introduction you should

describe the program, what it is; how it was written and description of input$/$output$.$