//
// CS 202 demonstration program 04
// Written by Dave Williams for 9/16/03 class 
//
// Program to demonstrate the use of recursive functions calculating Fibonacci
// numbers. Program timing was added because larger numbers took quite a while
// to process.
//
// The Fibonacci numbers are obtained by adding the two previous numbers in  
// the series: F(0) = 0, F(1) = 1, F(2) = 0 + 1 = 1, F(3) = 1 + 1 = 2, 
// F(4) = 2 + 1 = 3, F(5) = 3 + 2 = 5, F(6) = 5 + 3 = 8, F(7) = 8 + 5 = 13,
// etc.
//

unsigned long int Fibon(long int);

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main()   
{   

   long int a;
   clock_t start, stop;
     
   cout << "\n\nProgram to compute the Nth Fibonacci number.";
   
   do
   {
      cout << "\n\n\n\nInput N (-1 to quit) : ";
      cin >> a;

      if (a == -1)                  
         exit(0);

      if (a > 47)
         cout << "\nCan't do that - it's too large!";         
         
      else
         a = abs(a);    // forces the input to be positive

      start = clock();

      cout << "\nFibonacci Number F(" << a << ") = " << Fibon(a) << ". ";

      stop = clock();

      cout << endl << endl << "Total runtime: "
           << (stop - start) / (CLOCKS_PER_SEC / double (1000.)) << " ms.";

   } while(1);

   return 0;       
}


unsigned long int Fibon(long int n) 
{    
   if (n < 2)                     
      return n;                        
   else
      return (Fibon(n-1) + Fibon(n-2));                
}