#include <iostream>
using namespace std;
 
int find_fib(int);    
 
int main(int argc, char* argv[])
{
  int n=0, result=0;
  cout << "Enter the position in the sequence to find: ";
  cin >> n;
  result = find_fib( n );
  cout << result << " is the " << n << "th Fibonacci sequence number" << endl;
  system("pause");
  return 0;
}
 
int find_fib( int n )
{
  if(n < 3)
    return 1;
  else
    return( find_fib(n - 2) + find_fib( n - 1 ) );
}

int theFact = 1;
for(int i=N; i>0; i--)
{
     theFact *= i;
}
 
return theFact;

int fib(int n){
 
  int previous = -1;
  int result   = 1;
  int sum;
 
  for(int i = 0; i <= n; i++){
    sum = previous + result;
    previous = result;
    result   = sum;
  }
 
  return result;
}

#include <iostream>
#include <ctime> //for calculating execution time
 
double diffclock(time_t ,time_t ); //for calculating execution time
int find_fib(int);    
unsigned long double fibWrapper(int);
unsigned long double fibo_find_2 (unsigned long double, unsigned long double, int);
unsigned long double fibo_find_3_NonRecursive(int);
 
int main(int argc, char* argv[])
{
	//Required for measuring execution perfomance
	time_t startTime1,endTime1,startTime2;
        time_t endTime2,startTime3,endTime3;
	double elapsedTime1,elapsedTime2,elapsedTime3;
 
	int n=0;
	unsigned long double result=0;
	std::cout << "Enter the position in the sequence to find: ";
	std::cin >> n;
 
	//PART A:
	startTime1 = clock();	//Start measuring execution time
	result = find_fib(n);
	endTime1 = clock();	//Stop measuring execution time
       //Get total execution time in msec	
        elapsedTime1 = diffclock(endTime1,startTime1);
	std::cout <<"A: Your function gives: "<< result << " is the " 
                     << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART A is = "<<elapsedTime1
                    <<" msecs"<<std::endl;
	result = 0;
 
	//PART B:
	startTime2 = clock();	//Start measuring execution time
	result = fibWrapper(n);
	endTime2 = clock();	//Stop measuring execution time
       //Get total execution time in msec
	elapsedTime2 = diffclock(endTime2,startTime2);
	std::cout <<"B: Optimized function gives: " <<result << " is the " 
                     << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART B is = "<<elapsedTime2
                     <<" msecs"<<std::endl;
	result = 0;
 
	//PART C:
	startTime3 = clock();	//Start measuring execution time
	result = fibo_find_3_NonRecursive(n);	
	endTime3 = clock();	//Stop measuring execution time
        //Get total execution time in msec
	elapsedTime3 = diffclock(endTime3,startTime3);
	std::cout <<"C: Iterative function gives: " <<result << " is the " 
                      << n << "th Fibonacci sequence number" << std::endl;
	std::cout<<"The execution time of the PART C is = "<<elapsedTime3
                     <<" msecs"<<std::endl;
 
	return 0;
}
// PART A:
//Your recursive solution: Correct BUT VERY INEFFICIENT exponential performance
unsigned long double find_fib( int n )
{
	if(n < 3)
		return 1;
	else
		return( find_fib(n - 2) + find_fib( n - 1 ) );
}
 
//PART B:
//Optimized recursive solution: Correct and with O(n) performance
unsigned long double fibo_find_2(unsigned long double fibCurr,unsigned long double fibPrev, int n) //is called indirectly throuth the wrapper function
{
	//fibCurr: the current fibonacci Number
	//fibPrev: the previous fibonacci number
	//n: the number of the fibonacci numbers left to calculate
	if(n == 1)
		return fibCurr;
	else
		return fibo_find_2(fibCurr+fibPrev,fibCurr, n-1);
}
//The wrapper function for calculating fibonacci numbers
unsigned long double fibWrapper (int n)
{
//returns the value of the nth fibonacci number
	return fibo_find_2(1, 0, n);
}
 
//PART C:
////Non recursive==Iterative solution
unsigned long double fibo_find_3_NonRecursive (int n)
{
	unsigned long double localresult = 1;
	unsigned long double temp1 = 1;
	unsigned long double temp2 = 0;
 
	for (int k=3;k<=n;k++)
	{
		temp2 = localresult;
		localresult +=  temp1;
		temp1 = temp2;
	}
	return localresult;
}
//Nedded for calculating the execution time
double diffclock(time_t clock1,time_t clock2) //Using time_t & difftime
{
	double diffticks=difftime(clock1,clock2); 
	double diffms=(diffticks)/(CLOCKS_PER_SEC/1000);
	return diffms;
}