URI Online Judge Solutoin | 1029 Fibonacci, How Many Calls?

URI Online Judge | 1029

Fibonacci, How Many Calls?

By Neilor Tonin, URI  Brazil

Timelimit: 1

Sometimes when you are a Computer Science student, you’ll see an exercise or a problem involving the Fibonacci sequence. This sequence has the first two values 0 (zero) and 1 (one) and each next value will always be the sum of the two preceding numbers. By definition, the formula to find any Fibonacci number is:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2);

One way of finding Fibonacci numbers is by recursive calls. This is illustrated below, presenting the tree of derivation when we calculate fib(4), i.e. the fifth value of this sequence:

In this way,

• fib(4) = 1+0+1+1+0 = 3
• 8 recursive calls were done.

Input

The first input line contains a single integer N, indicating the number of test cases. Each test case contains an integer number X (1 ≤ X ≤ 39) .

Output

For each test case we will have an output line, in the following format: fib(n) = num_calls calls = result, where num_calls is the number of recursive calls, always with a space before and after the equal sign, as shown below.

Input Sample	Output Sample
2 5 4	fib(5) = 14 calls = 5 fib(4) = 8 calls = 3

URI Online Judge Solutoin | 1029 Fibonacci, How Many Calls? in C language

#include <stdio.h>

 

int counter, call;

 

int fib(int n)

{

    if(n == 0){

            call++;

            return 0;

    }else if(n == 1){

            call++;

            counter++;

            return 1;

    }else{

            call++;

            return fib(n - 1) + fib(n - 2);//call recursively

    }

}

 

int main()

{

    int n, i, x, res;

    scanf("%d", &n);

 

    for (i = 0; i < n; ++i)

    {

        counter = 0;

        call = 0;

        scanf("%d", &x);

        res = fib(x);

        printf("fib(%d) = %d calls = %d\n", x, call - 1, counter);

    }

 

        return 0;

}

See or download from Dropbox
See main Link in URI online Judge

Some Description : 

URI Online Judge  | 1029 Fibonacci, How Many Calls? is a simple recursive program.TO solution this URI 1029 Fibonnaci number problem using recursion, I've just applied the rules of recursion.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).[1] The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.--From Wikipedia

Recursion is the process of repeating items in a self-similar way. In programming languages,if a program allows you to call a function inside the same function, then it is called a recursive call of the function.- From TutorialsPoint

Recursion is a function calling which call itself inside the function.

In the line,

return fib(n - 1) + fib(n - 2);//call recursively

I've just using the recursion method. If n != 0 and n != 1 then come to the recursion.
Recursion will continuous until the if statement becomes false.
And we know that in fibonacci number the method of get the fibonacci is 
fib = fib1 + fib0

So it's the short desciption on the fibonacci problem, since you face any problem in this question, please knock us below by commenting.Thanks