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,

Answer 1

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

Answer 2

Is there any relation for this problem ?

There is a close-form equation for the nth fibonacci number: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

In the pseudocode you posted, the number of calls satisfies the recurrence relation

x(n) = x(n-1) + x(n-2) +1   # for n>=2
x(1) = 1
x(0) = 1

This is almost same as the Fibonacci recurrence relation. Proof by induction can show that the number of calls to fib made by fib(n) is equal to 2*fib(n)-1, for n>=0.

Of course, the calculation can be sped up by using the closed form expression, or by adding code to memorize previously computed values.

Answer 3

As mentioned above, you need to solve the following recurring equation: K(n)=K(n-1)+K(n-2)+1

Let's write it for n-1: K(n-1)=K(n-2)+K(n-3)+1

Now, subtract the second one from the first one: K(n)-K(n-1) = K(n-1) - K(n-3),

or

K(n) - 2*K(n-1) + K(n-3) = 0.

The respective characteristic equation will be: x^3 - 2*x^2 + 1 = 0.

It has the following roots: 1, (1+sqrt(5))/2, (1-sqrt(5))/2

Thus for any real A,B,C the following function K(n) = A*(1)^n + B*((1+sqrt(5))/2)^n + C*((1-sqrt(5))/2)^n

will be a solution for your equation.

To find A,B,C you need to define several initial values K(0), K(1), K(2) and solve the system of equations.

Answer 4

phi is a constant

position = ceil(log((n - 0.5)*sqrt(5))/log(phi));

n is the fibonacci number... position will give you the which fibonacci number is n

for example given 13 , position will be 7 - 0 1 1 2 3 5 8 13

using this position just calculate the fibonacci number at position-1 or any position you want relative to given fibonacci number.

Previous Fibo Num = floor((pow(phi,position-1)/sqrt(5))+0.5);

floor((pow(phi, position)/sqrt(5))+0.5) - is the standard formula for calculating Nth fibonacci num (Note - This is not an approximation)

I have just reverse this formula to calculate the position and use the position - 1 to calculate the previous fibonacci number.

Ref - http://itpian.com/Coding/20951-Given-the-Nth-fib-no-and-find-the--N-1-th-fib-number-without-calculating-from-the-beginning---------.aspx

Answer 5

This is a classic problem for solving with Recurrence Relations.

Specifically, the fibonacci problem has the following parameters:

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2)

Once you master solving recurrences, you'll have no problem reaching the solution (which, incidently, is exactly the same as fib(n)).

Answer 6

Interesting question, I can't give you a formula, but I wrote a Ruby program to do it, it works on numbers I figured out on paper, and it should work for any.

#!/usr/bin/ruby
#find out how many times fib() would need to be called

def howmany(n)
    a = [ ]
    a.push n-1
    a.push n-2
    while a.select{|n| n > 2}.length > 0
        a.map! do |n|
            n > 2 ? [n-1,n-2] : n
        end
        a.flatten!
    end
    a.length
end

.

>> howmany(10)
=> 55

It's slow.. I'm figuring out 35 right now, I'll edit when it finishes.

Edit:

>> howmany(35)
=> 9227465