Recursive Palindrome Test

Question

I have a prototype restriction of bool pal(char str[], int length) and I need to test whether a string the user entered is a palindrome or not. The code I have is:

bool pal(char str[], int length)
{
    if(*str == str[length - 1])
    {
        pal(str+1, length-1);
    }
    else
    {
        return false
    }
    return true;
}

but it seems to only be testing if the first character is the same as the last character. I think this is because my array (start point) isn't incrementing but I'm not sure why.

Answer 1

I suppose it's probably due to some deep-seated aversion to if statements, but if it were up to me, I think I'd write the code something like this:

bool pal(char *str, size_t len) { 
    return len <2 || (str[0] == str[len-1] && pal(str+1, len-2));
}

Answer 2

Here is a working version of your code.

bool pal(const char* str, int length)
{
   if(length <2) return true; // base case - 1 or 0 length string is a palindrome.
   if((*str) == str[length - 1])
   {
     return pal(str+1, length-2); // -2 because 1 from front and 1 from back. 
   }
   else
   {
     return false;
   }
    //no return here because the recursive call is returned.
}

Answer 3

Your main problem is that you don't do anything with the result of the recursive call:

 if(*str == str[length - 1])
    {
        pal(str+1, length-1);
    }

should probably be:

 if(*str == str[length - 1])
    {
        return pal(str+1, length-1);
    }

You also need to check for such things as a zero length string or string with only a single character.

Answer 4

You check first and last character, so you should decrease length by 2, not by 1. Also, you should return the value of internal pal call, not throw it away.

if(*str == str[length - 1])
{
    return pal(str + 1, length - 2);
}

An additional test for length being >=2 and str being not null would be in order too.