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

0 as find_fib will never be called.

Answer 2

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 3

Is there any relation for this problem ?

There is a close-form equation for the nth fibonacci number: http://en.wikipedia.org/wiki/Fibonacci%5Fnumber#Closed%5Fform%5Fexpression

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 4

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 5

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