Move into the directory hard and create the file fibcount.c . You will write a p

Question

Move into the directory hard and create the file fibcount.c.

You will write a program which takes in a number, say n, and displays the nth Fibinacci number and the number of recursive calls needed. One way to do this is to use a global variable which increments each time the recursive function is called.

Recall that the recurrence relation for generating Fibonacci numbers is

The implementation of the Fibonacci recurrence rapidly increases in the amount of time to compute a Fibonacci number. We recommend numbers in the 1-20 and to try larger numbers going up by 1 each time to see the difference in the number of recursive calls it makes.

For example

Here is another run

Explanation / Answer

Here is the code for you.

I believe the sample outputs provided are not correct. fib(5) will call the function recursively only for 9 times, and not for 123 times.

fib(5) = fib(4) + fib(3)

= fib(3) + fib(2) + fib(2) + fib(1)

= fib(2) + fib(1) + 1 + 1 + 1

= 1 + 1 + 1 + 1 + 1

Anyways, here the code for you.

#include <stdio.h>
int count = 0;
int fibonacci(int n)   /*Call the function.*/
{
count++;               /*Increment the count.*/
if(n == 1 || n == 2)   /*If n value is either 1 or 2, return 1.*/
return 1;
else                   /*Else call the function recursively.*/
return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
int num, fact;
printf("Enter an integer: ");   /*Read the value of n.*/
scanf("%i", &num);
fact = fibonacci(num);       /*Call the function.*/
printf("fib(%i) is %i and has %i recursive calls. ", num, fact, count);
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.