Question

Write a short recursive C++ function that determines if a string s is a palindrome, that is, it is equal to its reverse. For example,"racecar" and "gohangasalamiimalasagnahog" are palindromes. Please include the pseudo code so that I can understand better with simple English as much as possible.

Answer 1

Code:

#include<iostream>
using namespace std; 
  

bool isPalRec(char str[],  
              int s, int e) 
{ 
      
    // If there is only one character 
    if (s == e) 
    return true; 
  
    // If first and last 
    // characters do not match 
    if (str[s] != str[e]) 
    return false; 
  
    // If there are more than  
    // two characters, check if  
    // middle substring is also  
    // palindrome or not. 
    if (s < e + 1) 
    return isPalRec(str, s + 1, e - 1); 
  
    return true; 
} 
  
bool isPalindrome(char str[]) 
{ 
    int n = strlen(str); 
      
    // An empty string is palindrome
    if (n == 0) 
        return true; 
      
    return isPalRec(str, 0, n - 1); //passing index of the string to be checked
} 
  
// Driver Code 
int main() 
{ 
    char str[] = "racecar"; 
  
    if (isPalindrome(str)) 
    cout << "Yes"; 
    else
    cout << "No"; 
  
    return 0; 
} 

Output:

Code screenshot:

The pseudocode for isPalRec(char str[],int s,int e) is explained below:

s is the starting index of the string while e is the ending index of the string.

The base cases for the recursive method are as follows:

If the values of s and e match, then true is returned, meaning the string is palindrome.

If the value at str[s] and str[e] do not match, then the strings are not palindrome and false is returned.

In the next check, if the value of s < e+1, then we recursively call our method. In the call, we increment the value of s by 1 and decrement the value of e by 1. Thus s is moving forward in the string and e is moving backward with each call.

If none of the above conditions is true, then our method returns true which implies that the string is palindrome.