#include <sys/time.h>
#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

//declare funciton prototypes
int getNum();
long int fib_it(int);
long int fib_rec(long int);

int main()
{
   //define local variables
   long int fibNum = 0;
   int nth;   
   char whatDo;
   typedef struct timeval time;


   time stop, start;
   
   //get the nth number you want
   nth = getNum();

   //ask if iterative or recursive
   cout << "(i)erative or (r)ecursive?: ";
   cin >> whatDo;

   //get current time of day for start of program
   gettimeofday(&start, NULL);

   if(whatDo == 'i')
   {
      fibNum= fib_it(nth);
   }
   else if(whatDo == 'r')
   {
      fibNum = fib_rec(nth);
   }

   //print out the stuff to the user
   cout << "The " << nth << "nth Fibonaci number is " << fibNum << endl; 
   
   //get time at end of program
   gettimeofday(&stop, NULL);

   if(stop.tv_sec > start.tv_sec)
   {
      cout << "Seconds: " << stop.tv_sec-start.tv_sec << endl;
   }
   else
   {
      cout << "Micro: " << stop.tv_usec-start.tv_usec << endl;
   }

   return 0;
}

//get the number in the sequence from the user
int getNum()
{
   //initialize local variables
   int num;

   //prompt user
   cout << "Enter the point in the Fibonacci sequence you want to calculate: ";
   cin >> num;

   return num;
}

long int fib_it(int num)
{
  //initialize local variables
  long int first = 1, sec = 1, next=1;

  for(int i = 1; i <= num-2; i++)
  {
     next = first + sec;
     first = sec;
     sec = next;
  }

  return next;
}

long int fib_rec(long int num)
{
   if (num == 1)
   {
   	return 1;
   }
   else if(num <= 0)
   {
      return 0;
   }
   else
   {
      return fib_rec(num -1) + fib_rec(num-2); 
   }
}