CODEWITHSUNDEEP
c++recursioncharacter-arrays
Derp
Derp

Reputation: 929

Recursive Palindrome Test

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.

Upvotes: 1

Views: 6034

Answers (4)

Spook
Spook

Reputation: 25927

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.

Upvotes: 1

Michael Burr
Michael Burr

Reputation: 340208

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.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490108

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));
}

Upvotes: 4

Karthik T
Karthik T

Reputation: 31952

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.
}

Upvotes: 4

Related Questions