title: Counting number of recursive calls in fibonacci, in C
body: <p>I faced the following question:</p>
  
  <p>Calling <code>fib(8)</code> (below), how many recursive calls are made (ignoring the first) ? And what's the return value?</p>
  
  <pre><code>int fib (int n) {
      if (n==0 || n==1) return 1;
      else return fib(n-1) + fib(n-2);
  }
  </code></pre>
  
  <p>So I did:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  int r = 0;
  
  int fib (int n) {
      printf("k: %d fib n: %d", r++, n);
      if (n==0 || n==1) {
          printf("\n");
          return 1;
      } else { 
          printf(" +\n");
          return fib(n-1) + fib(n-2); 
      }
  }
  
  int main(int argc, char **argv) {
      int n = atoi(argv[1]);
      int f = fib(n);
      printf("\nreturn: %d\n", f);
      return 1;
  }
  </code></pre>
  
  <p>Using this I'll answer <code>fib(8) = 34</code> the number of recursive calls is <code>66</code>.</p>
  
  <p>Am I right?</p>