Consider the following code snippet:

```
int fib(int N)
{
if(N<2) return 1;
return (fib(N-1) + fib(N-2));
}
```

Given that `fib`

is called from main with N as 10,35,67,... (say), how many total calls
are made to `fib`

?

Is there any relation for this problem?

PS: This is a theoretical question and not supposed to be executed.

EDIT:

I am aware of other methods for the faster computation of Fibonacci series.

I want a solution for computing number of times fib is invoked for fib(40),fib(50) ,.. without the aid of compiler and in exam condition where you are supposed to answer 40 question similar to this one in a stipulated of time ( about 30 mints).

Thanks,

Let *f(n)* be the number of calls made to calculate `fib(n)`

.

- If
*n < 2*then*f(n) = 1*. - Otherwise,
*f(n) = 1 + f(n - 1) + f(n - 2)*.

So, *f* is at least *O(fib(n))*. In fact, *f(n)* is *2 * fib(n) - 1*. We show this by induction:

- Base cases (
*n < 2*, that is,*n = 0*or*n = 1*):*f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1*.

- Induction step (
*n >= 2*):*f(n + 1) = f(n) + f(n - 1) + 1**f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1**f(n + 1) = 2 * fib(n + 1) - 1*

There exist efficient ways to calculate any Fibonacci term. Thus the same holds for *f(n)*.

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow