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

Jinku Hu Feb 02, 2024

C++ C++ String

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

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

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::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

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::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

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::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

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

Author: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Use Recursive Function to Check for a Palindrome String

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

Related Article - C++ String

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