//    CIS 235 -   Recursion 
#include <iostream>
#include <ctime>
using namespace::std;

int  factR(int);

int  searchR(const int data[], int first, int last, int lookFor);

int  binarySearchR(const int data[], int first, int last, int lookFor);

int  combinations(int group, int members);

int  combinationsD(int group, int members);  // debug information

int  combinationsDFast(int group, int members);  // Remember previous answers

void printReverseR(const char data[]);

//  Write the following function in class
//   I - iteration, use a loop
//   R - recursion, call the function recursively

int  factI(int);   

int  searchI(const int data[], int first, int last, int lookFor);

int  binarySearchI(const int data[], int first, int last, int lookFor);

int  sumI(const int data[], int cellsUsed);

int  sumR(const int data[], int cellsUsed);

int  stringLengthI(const char * p);

int  stringLengthR(const char * p);

bool smallerI(const char * left, const char * right);

bool smallerI(const char * left, const char * right);

int  largestI(const int data[], int cellsUsed);

int  largestR(const int data[], int cellsUsed);

unsigned measure1 = 0;   // used to compare the combinations functions
unsigned measure2 = 0;


void main()
{
	cout << factR(6) << endl;

	int data[5] = { 6, 2, 9, 8, 3};
	cout  << searchR(data,0,4,8) << endl
		  << searchR(data,0,4,1) << endl;
	cout  << combinations(6,3) << endl;
	printReverseR("day after tomorrow");
	cout << endl;
	int sorted[6] = { 23, 45, 78, 124, 199, 204};
	cout  << binarySearchR(sorted,0,5,199) << endl
		  << binarySearchR(sorted,0,5,23) << endl
		  << binarySearchR(sorted,0,5,67) << endl;

	int com ;
	cout << "Starting combinations " <<time(0)<< endl;
	com = combinations(56,8);
	cout << "Ending combinations " << measure1 << " " << time(0) << endl;
	cout  << "56 things taken 8 at a time is " << com << endl;

	cout  << "Now using faster function" << endl;
	cout << "Starting combinationsDFast " << time(0) <<  endl;
	com = combinationsDFast(56,8);
	cout << "Ending combinationsDFast " << measure2 << " " << time(0) << endl;
	cout  << "using  fast 56 things taken 8 at a time is " << com << endl;

	return;
}

// ******************************************************************

int factR(int n)
{
	if ( n == 0 ) return 1;
	return n * factR(n-1);
}
int fact2R(int n)
{
    //  use of work variable to illustrate activation frames
    if ( n == 0 ) return 1;
	int partial;
	partial = fact2R(n - 1 );
	int answer;
	answer = partial * n;
	return answer;
}

//   Linear Search
int searchR(const int data[], int first, int last, int lookFor)
{
	if ( lookFor == data[first] ) return first;
	if ( first   == last        ) return -1;
	return searchR(data,first+1,last,lookFor);
}

//  Binary Search
int binarySearchR(const int data[], int first, int last, int lookFor)
{
	if ( first > last )          return - 1;
	int mid = (first + last) /2;
	if ( lookFor == data[mid] ) return mid;
	if ( lookFor <  data[mid] ) return binarySearchR(data,first,mid-1,lookFor);
	return                             binarySearchR(data,mid+1,last,lookFor);
}

//  Print a C++ string in reverse order
void printReverseR(const char * p)
{
	if ( *p == '\0') return;
	printReverseR(p + 1);
	cout << *p;
}

//  combinations of group things taken members at a time
int combinations(int group, int members)
{
	measure1++;
	if ( members == 1    ) return group;
	if ( members == group) return 1;
	return combinations(group - 1, members - 1)
		 + combinations(group - 1, members    );
}


//  count activation frames and depth of recursion
int combinationsD(int group, int members)
{
	static int activationFrameCounter = 0;
	int localActivationFrameNumber = ++activationFrameCounter;
	static int maxDepth = 0;
	static int currentDepth = 0;
	currentDepth++;
	if ( currentDepth > maxDepth)
		 maxDepth = currentDepth;
	if ( members == 1    )
	{
		currentDepth--;
		return group;
	}
	if ( members == group)
	{
		currentDepth--;
		return 1;
	}
	int left  = combinationsD(group - 1, members - 1);
	int right = combinationsD(group - 1, members    );
	if (localActivationFrameNumber == 1 )
	{
		cout << "Total activation frames was " << activationFrameCounter << endl;
		cout << "The maximum depth was " << maxDepth << endl;
	}
	currentDepth--;
	return left + right;
}

//  Use static array to save previous answers
//  Count activation frames and depth
int combinationsDFast(int group, int members)
{
	static int answers[60][600];
	measure2++;	
	if ( members == 1    )
	{
		return group;
	}
	if ( members == group)
	{
		return 1;
	}
	if ( answers[group][members] != 0 )
	{
		return answers[group][members];
	}
	int left  = combinationsDFast(group - 1, members - 1);
	int right = combinationsDFast(group - 1, members    );
	answers[group][members] = left + right;
	return left + right;
}

/*
720
3
-1
20
worromot retfa yad
4
0
-1
Starting combinations 1286820542
Ending combinations 405855468 1286820575
56 things taken 8 at a time is 1420494075
Now using faster function
Starting combinationsDFast 1286820575
Ending combinationsDFast 673 1286820575
using  fast 56 things taken 8 at a time is 1420494075
Press any key to continue . . .

From calculator found on the internet
C(56,8) = 56! / 8! (56 - 8)! =
1420494075
*/