title: Number of calls for nth Fibonacci number
body: <p>Consider the following code snippet:</p>
  
  <pre><code>int fib(int N)
  {
     if(N&lt;2) return 1;
     return (fib(N-1) + fib(N-2));
  }
  </code></pre>
  
  <p>Given that <code>fib</code> is called from main with N as 10,35,67,... (say), how many total calls
  are made to <code>fib</code>?</p>
  
  <p>Is there any relation for this problem?</p>
  
  <p>PS: This is a theoretical question and not supposed to be executed.</p>
  
  <p>EDIT: </p>
  
  <p>I am aware of other methods for the faster computation of Fibonacci series.</p>
  
  <p>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).</p>
  
  <p>Thanks, </p>