title: Why is recursion taking so long?
body: <p>In using recursion to calculate the  nth number of the fibonacci sequence, I have written this simple program:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;limits.h&gt;
  
  unsigned int long long fibonacci(unsigned int number);
  
  //game of craps
  int main(int argc, char** argv)
  {
  
      for(int n = 1; n &lt;= 100; n++)
      {
          printf("%llu\n", fibonacci(n));
      }
  
      return (EXIT_SUCCESS);
  }
  
  
  unsigned long long int fibonacci(unsigned int number)
  {
      if (number == 0 || number == 1)
      {
          return number;
      }
      else
      {
          return fibonacci(number - 2) + fibonacci(number - 1);      
      }
  }
  </code></pre>
  
  <p>where each call to the n+1 number in the sequence doubles the number of function calls the program has to run.  Therefore the number of calls being made to the recursive function is something of 2^n, or exponential complexity.   Understood.  But where is all of the computing power going? once the nth number in the sequence starts to hit 40, the computer starts taking noticeable time to compute the result where at n = 47 its take 30+ seconds.  However my computer shows that I'm only using 21 percent of cpu power.  I'm using NetBeans IDE to run the program. It's a quad core system.  </p>