title: How many times does fib(3) gets called when we call fib(6) using the recursive approach to Fibonacci series?
body: <p>I came across the problem</p>
  <blockquote>
  <p>How many times does fib(n) gets called when we call fib(k) using the recursive approcah to Fibonacci series? (where k&gt;n)</p>
  </blockquote>
  <p>Here fib(n) is the function which gives nth fibonacci number using the recursive approach:-</p>
  <pre><code>    int fib(int n)
  {
      if (n &lt;= 1) return n; 
      return fib(n-1) + fib(n-2);
  } 
  </code></pre>
  <p><strong>MY TRY:</strong>
  I tried to do it for the particular case where n=3 and k=6. I found the answer to be fib(6-3+1) = fib(3+1) = 3. The following flowchart shows it.<br />
  <a href="https://i.stack.imgur.com/xeWRw.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xeWRw.jpg" alt="" /></a>
  Does it generalise too?
  Is it correct to state that the answer to this problem is fib(k-n+1)?</p>
  <p>P.S. Please do not just post some code in answer! Please try to think in terms of a general formulla.</p>