How to make this recursive function check if the string is a palindrome?

Question

The function should reverse the string and return true if it is the same backwards and forwards. I have to use recursion for this, and can't use reverse() for this. I ran my code through the debugger and it seems that my code returns false when it checks s == reverse.

Here's my attempt:

bool Palindrome(const string& s, int i){
string reverse;

    if(i < s.size()){
        reverse[i] = s[s.size()-(i+1)]; // first character in reverse is the last character in s
        Palindrome(s, i + 1);
        }       
    if(s == reverse){
        return true;
    }
    else{
        return false;
    }

}

What's your input string? If you ran your code through the debugger, why not just step into everything and see what is happening? — Tas, Feb 03 '20 at 05:10
Are [C recursive function palindrome](https://stackoverflow.com/questions/46558406/c-recursive-function-palindrome?r=SearchResults&s=1|90.9934) or [Recursive method for palindrome checkup](https://stackoverflow.com/questions/30168953/recursive-method-for-palindrome-checkup?r=SearchResults&s=3|86.1939) of no help? — David C. Rankin, Feb 03 '20 at 05:13
It has been a long time since I've played with C++, but the first thing I noticed is that string is not initialized, so you get some default size which may or may not be big enough. Secondly, you don't copy the null character, so the string might not be terminated correctly and thus a comparison would be false. — Frank Merrow, Feb 03 '20 at 06:09

score 0 · Answer 1 · answered Feb 03 '20 at 06:19

The following code shows an example implementation of what you elaborated in the question. It creates a reverse string using recursion, and then compares it to the reference string, and returns a boolean result.

Memory Complexity O(n). But in reality it does take an extra O(n) memory for the reversed string.

#include <iostream>
#include <algorithm>
using namespace std;

bool isPalindrome(string& reference, string& reversed, int index){
    if(index >= reference.size()/2){
        return reference == reversed;
    }

    int lastIndex = reference.size()-1;
    swap(reversed[index], reversed[lastIndex-index]);
    return isPalindrome(reference, reversed, index+1);
}

int main() {
    string ref = "abcdcba";
    string test = ref;
    cout << isPalindrome(ref,test,0) << endl;
    return 0;
}

score 0 · Answer 2 · answered Feb 03 '20 at 06:23

If you want Palindrome(const string&) to manipulate string reverse you should pass it by reference.

#include <string>
#include <iostream>

using namespace std;

bool palindrome_internal( const string& s, string& reverse, int i )
{
    if(i < s.size()){
        reverse[i] = s[s.size()-(i+1)]; // first character in reverse is the last character in s
        palindrome_internal( s , reverse , i + 1);
    }

    return s == reverse;
}

bool Palindrome(const string& s ){
    string reversed { s }; // initialized here

    return palindrome_internal( s , reversed , 0 ); // And passed to recursive function
}

int main()
{
    cout << Palindrome( "example" ) << endl; // Not palindrome
    cout << Palindrome( "repaper" ) << endl; // Palindrome
    cout << Palindrome( "rotator" ) << endl; // Palindrome
    cout << Palindrome( "madam" ) << endl; // Palindrome
    cout << Palindrome( "" ) << endl; // Palindrome
    cout << Palindrome( "" ) << endl; // Palindrome
}

online code

Your code actually a bit weird, because you are not calculating palindrome recursively, actually you are filling string reverse recursively.

Maybe this simpler version suits better.

#include <string>
#include <iostream>

bool palindrome( const std::string& s, int i = 0 )
{
    if ( i == s.size() )
        return true;

    return s[ i ] == s[ s.size() - i - 1 ] && palindrome( s , i + 1 );
}

int main()
{
    using namespace std;
    cout << palindrome( "example" ) << endl; // Not palindrome
    cout << palindrome( "repaper" ) << endl; // Palindrome
    cout << palindrome( "rotator" ) << endl; // Palindrome
    cout << palindrome( "madam" ) << endl; // Palindrome
    cout << palindrome( "" ) << endl; // Palindrome
    cout << palindrome( "a" ) << endl; // Palindrome
}

online code

How to make this recursive function check if the string is a palindrome?

2 Answers2