Recursive isPalindrome method

[0x4B47]

I written a recursive method which returns true if the string passed to it is a palindrome, I cannot seem to see why the logic isnt working. I've thrown in a bunch of 'cout' statement to see where its going wrong but I cannot see why!

char buffer[] = "radar";

bool isPalindrome( char b[], int lB, int hB );

int main()
{
	int lowerBound=0, upperBound=0;

	while( buffer[upperBound] != '\0' )
		++upperBound;

	if( isPalindrome( buffer, lowerBound, upperBound ) )
		cout << buffer << " IS a palindrome." << endl;
	else
		cout << buffer << " IS NOT a palindrome." << endl;

	return 0;
}

bool isPalindrome( char b[], int lB, int hB )
{
	if( lB == hB )
		return true;

	else if( b[lB] == b[hB] )
		return isPalindrome( b, lB+1, hB-1 );

	else
		return false;
}

Can anyone please help?
Kunal.

 

[0x4B47]

Sorry ignore that, I just realised that upperBound is being passed as 5 when it shoud be 4 as array elements start at 0. My bad.
Kunal.

 

[lionelhill]

Just a comment: using recursion here looks elegant but it makes a huge amount of underlying work compared to just scanning the string forwards and backwards comparing characters until you reach the middle.

 

[Zyrenthian]

Just one note:

In the case of an even length string... i believe you may crash

Take "ABBA"

Recursion 1: b[0] == b[3] so lets call recurstively
Recursion 2: b[1] == b[2] lets call recursively again
Recursion 3: b[2] == b[1] still good.... recursivly call
Recursion 4: b[3] == b[0] recursive again
Recursion 5: b[4] == b[-1] Uh-oh, reading from memory that you dont have.

If you change your if conditional to

if( lB >= hB )
return true;

you should be all set

Matt

 

[Zyrenthian]

One more thing IF you use CStrings, you could determine this quickly with a combination of MakeReverse and CompareNoCase

Matt

 

[0x4B47]

Dear fellow coders,

I did take all those things into consideration, I was just experimenting and wondering why it wasnt working, and then remembered the ++ im doing on the buffer with the upperbound was taking the null terminator '\0' into consideration, so i took out all the other crap like checking for even strings such as 'ABBA' out just for the sake of simplicity when i made the post.
But regardless, thanks alot for the feedback becoz i believe there is always something to be learnt from others.
Thanks guys.
Kunal.

 

[lionelhill]

Reminds me of a nice question I once saw for assembly: reverse the words of a string in place, without using any local variables, or extra storage of any kind (i.e. "this is a sentence" to "sentence a is this"). Quite fun, that one.

 

[PerFnurt]

and for the easily amused: Do it in O as well.

/Per

_{"It was a work of art, flawless, sublime. A triumph equaled only by its monumental failure."}

 

[lionelhill]

PerFnurt, that IS quiet interesting: it's quite difficult to think of a new solution when you have an old one in your head, and because the solution I had is already O I'm now utterly stuck trying to think of an in-place method that Isn't O... At least I'm easily amused.