#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(char* str, int end) {
	if (end<1) { return 1; } // we've passed center, it's true
	if (str[0] != str[end]) { return 0; } // character doesn't match, it fails
	// note, we move the front one, the end one
	// then the end another one, to allow for the front movement
	return isPalindrome(str+1, end-2); 
}

void checkPalindrome(char* str) {
	printf("'%s' is ", str);
	if(!isPalindrome(str, strlen(str)-1)) { printf("not "); }
	printf("a palindrome\n");
}

int main() {
	checkPalindrome("space cats");
	checkPalindrome("star rats");
}

bool recursivePalindrome(std::string str, unsigned int index = 0) {
    return (str[index] == str[str.length()-index-1] ? recursivePalindrome(str, ++index) : index > (str.length()/2) ? true : false);
}

bool recursivePalindrome(std::string str, unsigned int index = 0, unsigned int len = 0) {
    if (len == 0) len = str.length();
    return (str[index] == str[len-index-1] ? recursivePalindrome(str, ++index) : index > (len/2) ? true : false);
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;


bool recursivePalindrome(std::string str, unsigned int index = 0, unsigned int len = 0) {
	if (len == 0) len = str.length();
	return (str[index] == str[len-index-1] ? recursivePalindrome(str, ++index) : index > (len/2) ? true : false);
}

int isPalindrome(char* str, int end) {
	if (end<1) { return 1; } // we've passed center, it's true
	if (str[0] != str[end]) { return 0; }
	return isPalindrome(str+1, end-2); 
}

void makeRandPalandrome(char *buffer, int size) {
	char *head = buffer;
	char *tail = head + (size-2);
	int mid = (size-1)/2;
	
	buffer[size-1] = 0;
	while(mid-- >= 0) { *head++ = *tail-- = 'A' + (rand() % 26); }
}

void test(unsigned long size) {
	unsigned long start, elapsed;
	cout << "Testing for: " << size << endl;
	char *pal = new char[size];
	makeRandPalandrome(pal, size);
	string strPal(pal);
	
	start = clock();
	cout << isPalindrome(pal, strlen(pal)-1) << endl;
	elapsed = clock()-start;
	cout << elapsed << " millisecs for isPalindrome." << endl;
	
	start = clock();
	cout << recursivePalindrome(strPal) << endl;
	elapsed = clock()-start;
	cout << elapsed << " millisecs for recursivePalindrome." << endl;

	cout << endl << endl;
	
	delete pal;
}


int main ()  {
	srand ( time(NULL) );
	
	for(unsigned long i=0; i<10; i++) {
		test(10000 + (i*1000));
	}
	 
	 return EXIT_SUCCESS;
}

bool recursivePalindrome(std::string &str, unsigned int index = 0, unsigned int len = 0) {
	if (len == 0) len = str.length();
	return (str[index] == str[len-index-1] ? recursivePalindrome(str, ++index) : index > (len/2) ? true : false);
}