#include <time.h>
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

const double H = 1.0;


double fToIntegrate (double x)
{

	return pow (x, 0.5) + 5.0;
}

double Integrate (double firstX, double lastX)
{

	double midX = (firstX+lastX)/2.0;
	double rangeSize = fabs(lastX - firstX);

	if (rangeSize <= H) {
		return fToIntegrate (midX) * (rangeSize);
	}
	else {
		return Integrate (firstX, midX) + Integrate (midX, lastX);
	}
}

int Q3RecursiveFunc (int n) {

	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (n == 3) return 1;
	else if (n == 4) return 3;
	else if (n == 5) return 5;
	else {
		return Q3RecursiveFunc(n - 1) + Q3RecursiveFunc(n-5);
	}

}

int Q3IterativeFunc (int n) {

	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (n == 3) return 1;
	else if (n == 4) return 3;
	else if (n == 5) return 5;

	int lastFive[5] = {1, 1, 1, 3, 5};

	int currVal = 0;
	for (int i = 5; i < n; i++) {

		currVal = lastFive[4] + lastFive[0];

		lastFive[0] = lastFive[1];
		lastFive[1] = lastFive[2];
		lastFive[2] = lastFive[3];
		lastFive[3] = lastFive[4];
		lastFive[4] = currVal;
	}

	return lastFive[4];

}

void ClockRecursiveFunction () {

	clock_t  ltimeBefore, ltimeAfter;
    float timeDiff = 0.0; 
	for (int i = 50; i < 70; i++) {

		ltimeBefore= clock( );
		cout << "F("<<i << ") = ";
		cout << Q3RecursiveFunc (i) << "; ";
		ltimeAfter = clock( );
		timeDiff = ltimeAfter - ltimeBefore;
		cout << "time to execute= " << timeDiff << endl;
	}

}

void RunIterativeFunction () {
	
	for (int i = 50; i < 70; i++) {

		cout << Q3IterativeFunc (i) << endl;
	}

}


double RecursivePower (int x, int n) {

	if (n == 0) return 1;
	else if (n == 1) return x;
	else {
		if (n % 2 == 0) {
			double temp = RecursivePower (x, n/2);
			return temp * temp;
		}
		else {
			return x * RecursivePower (x, n-1);
		}
	}
}


double IterativePower (int x, int n) {


	double result = 1.0;
	
	while (n > 0) {
		if (n % 2 != 0) {
			result *= x;
		}
		n /= 2;
		x *= x;
	}
	
	return result;
}

int main ()
{

cout <<Q3RecursiveFunc (15);

	/*
	
	RunIterativeFunction ();

	ClockRecursiveFunction ();

	cout << "Area under the curve is " << Integrate (0, 30) << endl;

	cout << "3^5 = "<<RecursivePower (3, 5) << endl;
	cout << "3^5 = "<<IterativePower (3, 5) << endl;
	*/
	return 0;
}