#include <iostream>
#include <ctime>
 
using namespace std;
 
typedef int* IntPtr;
 
long iter(int n)
{
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) 
    {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}
 
int optRecur(int n, int array[]) 
{
	if (array[n] != 0) 
		return array[n];
	if ((n == 0) || (n == 1))
		array[n] = 1;
	else 
		array[n] = optRecur(n-1,array) + optRecur(n-2,array);
	return array[n];
} 
 
void optRecurHelp(int n) 
{
	int* a = NULL;
	a = new int[n];
	for(int i = 0; i <= n; ++i) 
		a[i] = 0;
	optRecur(n,a);
	delete [] a;
	a = NULL;
}
 
long recur(int n)
{
    if ( n == 0 || n == 1 )
		return 1;
    else 
        return recur(n - 1) + recur(n - 2);
}
 
long time(int n, int funct)
{
	double emptyLoop;
	double j;
 
	if(funct == 1)
	{
		clock_t start,end;
		start = clock();
		for (int i=0;i<100000000;i++)
			recur(n);
		end = clock();
		emptyLoop = end-start;
		double time_passed = static_cast<double>(end-start)/CLOCKS_PER_SEC;
		j = (((end-start)-emptyLoop)/100000000);
	}
	if(funct == 2)
	{
		clock_t start,end;
		start = clock();
		for (int i=0;i<100000000;i++)
			iter(n);
		end = clock();
		emptyLoop = end-start;
		double time_passed = static_cast<double>(end-start)/CLOCKS_PER_SEC;
		j = (((end-start)-emptyLoop)/100000000);
	}
	if(funct == 3)
	{
		clock_t start,end;
		start = clock();
		for (int i=0;i<100000000;i++)
			optRecurHelp(n);
		end = clock();
		emptyLoop = end-start;
		double time_passed = static_cast<double>(end-start)/CLOCKS_PER_SEC;
		j = (((end-start)-emptyLoop)/100000000);
	}
	return j;
}
 
int main()
{
	int num1;
	int num2;
 
	cout << "What number would you like to compute? " << endl;
	cin >> num1;
	cout << "What function (recursive=1, iterative=2, optimized recursive=3)? " << endl;
	cin >> num2;
	cout << time(num1,num2) << endl;
	return 0;
}