# Number of calls for nth Fibonacci number

### Question

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,

1
8
11/28/2009 11:35:16 AM

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).

11
11/15/2009 11:23:46 PM