Check for a Palindrome String With A Recursive Function in C++

  1. Use Recursive Function to Check for a Palindrome String
  2. Use the std::equal Algorithm Check for a Palindrome String

This article will explain several methods of checking for a palindrome string with a recursive function in C++.

Use Recursive Function to Check for a Palindrome String

A recursive function is the one that calls itself from the function body. A recursive method is not the optimal way to implement a palindrome checking algorithm. isPalindrome function takes three arguments and returns a boolean value to indicate if the passed string is a palindrome. The second and third arguments are used to store the beginning and end positions of the string sequence. As the first condition, we evaluate if the string length is 1, and if so, the function returns immediately with an affirmative value. Next, the first and the last characters are compared, and if not equal, the function returns false. Otherwise, the execution continues to check whether the string contains more characters in the middle of the current st and en positions. If the condition evaluates true, then the recursive call is made with shifted positions and the same string value. On the other hand, false condition forces function to return true.

#include <iostream>
#include <string>

using std::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;

bool isPalindrome(const string &s, size_t st, size_t en)
{
    if (s.length() == 1)
        return true;

    if (s[st] != s[en-1])
        return false;

    if (st < en + 1)
        return isPalindrome(s, st + 1, en - 1);

    return true;
}

int main(){
    string s1 = "radar";
    string s2 = "Was it a cat I saw";

    isPalindrome(s1, 0, s1.length()) ?
    cout << "s1 is a palindrome" << endl :
    cout << "s1 is not a palindrome" << endl;

    isPalindrome(s2, 0, s2.length()) ?
    cout << "s2 is a palindrome" << endl :
    cout << "s2 is not a palindrome" << endl;

    return EXIT_SUCCESS;
}

Output:

s1 is a palindrome
s2 is not a palindrome

Notice that the previous solution can’t identify the palindromes with mixed-case letters and spaces such as s2 object. So, we need to convert the string to the same case letters and remove any spaces to find all valid palindromes correctly. std::trasform algorithm and erase-remove idiom are used to parse the string to the compatible form for the isPalindrome function.

#include <iostream>
#include <string>

using std::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;

bool isPalindrome(const string &s, size_t st, size_t en)
{
    if (s.length() == 1)
        return true;

    if (s[st] != s[en-1])
        return false;

    if (st < en + 1)
        return isPalindrome(s, st + 1, en - 1);

    return true;
}

int main(){
    string s2 = "Was it a cat I saw";

    transform(s2.begin(), s2.end(), s2.begin(),
              [](unsigned char c){ return tolower(c); } );
    s2.erase(remove(s2.begin(), s2.end(), ' '), s2.end());


    isPalindrome(s2, 0, s2.length()) ?
    cout << "s2 is a palindrome" << endl :
    cout << "s2 is not a palindrome" << endl;

    return EXIT_SUCCESS;
}

Output:

s2 is a palindrome

Use the std::equal Algorithm Check for a Palindrome String

std::equal is part of the C++ Standard Template Library and can be utilized to compare ranges. Thus, since the string class has the iterator interface, we can specify its range with begin and rbegin functions. Note though, the following std::equal overload version takes three arguments, the first two of which specify the first range, while the third argument denotes the beginning of the second range.

#include <iostream>
#include <string>

using std::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;

bool checkPalindrome(string& s) {
    string tmp = s;
    transform(tmp.begin(), tmp.end(), tmp.begin(),
              [](unsigned char c){ return tolower(c); } );
    tmp.erase(remove(tmp.begin(), tmp.end(), ' '), tmp.end());

    if (equal(tmp.begin(), tmp.begin() + tmp.size()/2, tmp.rbegin())) {
        return true;
    } else {
        return false;
    }
}

int main(){
    string s1 = "radar";
    string s2 = "Was it a cat I saw";

    checkPalindrome(s2) ?
    cout << "s2 is a palindrome" << endl :
    cout << "s2 is not a palindrome" << endl;

    return EXIT_SUCCESS;
}

Output:

s2 is a palindrome
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - C++ String

  • Parse String Using a Delimiter in C++
  • Convert String Into Binary Sequence in C++