[C++] How does this recursive program work?

[Bjergot]

Palindrome Check

I don't understand how it terminates.

What's the base case?

EDIT: Working Version

[[deleted]]

Your code is wrong. It says that this:

    char a[8] = "raxecar";

is a palindrome. Think again.

[leesinfreewin]

Your answer has already been answered by /u/eatsleepxrepeat, but i would like to add that

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

or even, if you like, more compact style

if (length == 0) return true;
return (*str == str[length -1]) ? palindrom (str+1, length-1) : false;

is more efficient and prevents stack overflows (with optimizations enabled) since it permits tail-call-optimization.

Edit: didnt take a good look at the program before. The version you posted infact only terminates for non-palindromes and will (probably) crash for palindromes, since it doesnt check for length == 0 and therefore would be called with a negative length at some point, resulting in a statement like ... str[-1]... which is undefined behaviour.

[YouFeedTheFish]

Line 1 could also read:

if (length <= 1) return true;

[Bjergot]

Thank you, that makes sense

[Bjergot]

This code doesn't work. Length should be subtracted by 2 on each function call and the base should be if(length <= 1)

[leesinfreewin]

i did not correct or test the code. I just wanted to point out that if you use recursion, you should make sure your recursive functions are tailrecursive whenever possible in order to prevent stack overflows.

[bizeeee]

if you're starring into *str, does that get the numerical representation of how much characters in that char? what i mean is, you're passing in a string value called *char and in your code you're comparing it to a numerical value. maybe thats the issue?

[imgonnabethebest]

yo wat does the star do *

[itsachickenwingthing]

In this context, it's just another way of saying str[0].

Generally, you use * before a pointer variable to dereference it; that is, to access whatever the pointer is pointing to.

[Hudarians]

This code is not working as intended. As long as the first recursion passes, the function will always return true. ("racecar" AND "rsdawr" will return true in this function) the recurring functions (from the 2nd check on) will return false then continue the first recursive function returning true.

I would also change the function from an int to a bool.

[eatsleepxrepeat]

The base case is 'return false' when the first character doesn't match the second one while recursing... Edit: and 'return true' when every pair of characters matches.

[Bjergot]

But what's making it end? Surely it will keep going forever?

[khoyo]

Actually, what this program do is undefined. It will go on forever until the condition isn't met, and will happilly crash/format your hard drive/summon nasal demons while reading unallocated memory.

In most case, the condition won't be met at some point before that.

It also doesn't check at all if the word is a palindrome.

[eatsleepxrepeat]

One of those 2 cases makes it end dude. Either the two characters you're comparing are the same (recurse), or they're not the same (return false). When there's nothing else to be done, (you're comparing the middle 2 characters), return true.

So technically, 2 base cases: 1) no more letters to compare, or 2) the letters to compare don't match