#include <iostream>
#include <string>
using namespace std;

//Return x^n
//Run time?: O(n)
double power(double x, int n)
{
	if (n==0) //base case
	{
		return 1;
	}
	else  //recursive case
	{
		double smallResult = power(x, n - 1);
		return x * smallResult;
	}
}

//solve faster?
//Run time: O(log n)
double fastPower(double x, int n)
{
	if (n==0)
	{
		return 1;
	}
	else
	{
		double halfpow = fastPower(x, n / 2); //C++ always rounds down for integer division

		if ( n % 2 == 0 ) //n is even
		{
			return halfpow * halfpow;
		}
		else //n is odd
		{
			return x * halfpow * halfpow;
		}
	}
}


//Return nth Fibonacci number
int fib(int n)
{
	if (n<=1) //base case
	{
		return n;
	}
	else //recursive case
	{
		return fib(n - 1) + fib(n - 2);
	}
}


//Assume start <= end
void printList(double * A, int start, int end )
{
	if (start == end) //base case
	{
		cout << A[start] << endl;
	}
	else //recursive case
	{
		cout << A[start] << endl;
		printList(A, start + 1, end);
	}
}

void printReverse(double * A, int start, int end)
{
	if (start == end) //base
	{
		cout << A[start] << endl;
	}
	else  //recursive
	{
		printReverse(A, start + 1, end);
		cout << A[start] << endl;
	}
}

int main()
{
	//Challenge #4:
	cout << power(3, 4) << endl;
	cout << fastPower(3, 4) << endl;
	cout << endl;

	//Challenge #5: compute nth fibonacci number
	cout << fib(9) << endl;  //34
	cout << fib(15) << endl; //???
	cout << endl;

	double nums[] = { 13.8, 2.14, 51, 82, 3.14, 1.7, 4.89, 18, 5, 23.6, 17, 48, 5.6 };

	//Challenge #6: print the list from given range
	printList(nums, 0, 12); //13.8 2.14 51 .... 48 5.6
	cout << endl;

	//Challenge #7: print the list, but backwards
	printReverse(nums, 0, 12); //5.6 48 17 ... 2.14 13.8
	cout << endl;
							   /*
	//Challenge #8: reverse order of items in list
	reverse(nums, 0, 12); 
	printList(nums, 0, 12); //5.6 48 17 ... 2.14 13.8

	//Challenge #9: locate minimum item in list
	cout << findSmallest(nums, 0, 12) << endl; //5 because 1.7 is at index 5

	//Challenge #10: sort the list
	sort(nums, 0, 12);
	printList(nums, 0, 12); //1.7 2.14 ... 48 51

	*/

	return 0;
}