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.

Please paste your actual code -- this doesn't look like it should even compile (e.g., `*pal == pal[length - 1]` should undoubtedly be `*str == str[length - 1]`). — Jerry Coffin, Feb 04 '13 at 06:58

score 4 · Answer 1 · answered Feb 04 '13 at 07:12

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

score 4 · Accepted Answer · answered Feb 04 '13 at 07:18

4

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

answered Feb 04 '13 at 07:18

Jerry Coffin

476,176
80
629
1,111

Could be a bit problematic... I usually try not to rely on operands evaluation order since it's not always obvious and easily broken by inexperienced maintainers. – SomeWittyUsername Feb 04 '13 at 07:22
2

@icepack: the thought of somebody being a maintainer if they don't know what `||` and `&&` mean is more than a bit scary (at least to me). – Jerry Coffin Feb 04 '13 at 07:27
the problem is not with understanding the meaning of `||` and `&&` but with the evaluation order in `C`. As far as pure math is concerned there is no difference if the left operand is evaluated first or the right. However, there is a big difference during runtime. Your code may be a simple example, but in a more complex cases the problematics might not be so obvious... Sorry if I'm being too picky. By the way: http://stackoverflow.com/questions/7112282/order-of-evaluation-of-operands – SomeWittyUsername Feb 04 '13 at 07:31
@icepack: Neither `||` nor `&&` is defined by mathematics. They're C (and C++) operators, and anybody who even touches C or C++ code should certainly know what they mean (including evaluation ordering). – Jerry Coffin Feb 04 '13 at 07:33
@icepack: The whole *point* of `&&` and `||` is their evaluation order. How can anyone intentionally use them without knowing their order?! – user541686 Feb 04 '13 at 07:46
@Mehrdad The whole point of `||` and `&&` is to correctly perform the required logical operation. Evaluation order is secondary – SomeWittyUsername Feb 04 '13 at 14:39
@icepack: But short-circuit evaluation is clearly a *major* part of the definition of the logical operation they perform. – Jerry Coffin Feb 04 '13 at 14:42
@JerryCoffin of course, not arguing that. This is however still secondary to performing the actual boolean operation – SomeWittyUsername Feb 04 '13 at 15:20
@icepack: Not in my mind -- in my mind, if the boolean was the only thing you cared about, you could as well say `!!a & !!b`. People use `&&` *because* of the short-circuiting (and to avoid saying `!`, but that's more minor). – user541686 Feb 04 '13 at 18:18
@Mehrdad People usually use `&&` when they want to express `if a AND b are both true`. Any other usage is a consequence of this, including the short-circuiting that allows not to evaluate `b`. – SomeWittyUsername Feb 04 '13 at 21:25
@icepack: Well, I disagree. :P – user541686 Feb 04 '13 at 21:25

Spook · Answer 3 · 2013-02-04T07:43:34.373

1

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.

edited Feb 04 '13 at 07:43

answered Feb 04 '13 at 07:02

Spook

25,318
18
90
167

Michael Burr · Answer 4 · 2013-02-04T07:19:04.880

1

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.

edited Feb 04 '13 at 07:19

answered Feb 04 '13 at 07:06

Michael Burr

333,147
50
533
760

@icepack: I disagree. For the initial call, "false" cannot be returned unless the first and last characters are not equal. Under all other circumstances, "true" is returned for the "main" call. – Kirby Feb 04 '13 at 07:17

Recursive Palindrome Test

4 Answers4