Home » Interview Questions » String Interview Questions » Recursive Palindrome check

Recursive Palindrome check


()

Write a recursive function to check if given string is palindrome or not.

Examples

Racecar – is a palindrome.
Racing – is not a palindrome

Time complexity : O(logn)

Algorithm

1. Traverse the input string.

2. If length of string is 1, return True.

3. Else, compare first and last characters and apply recursion to the remaining sub-string.

C++ Program

#include <bits/stdc++.h>

using namespace std;

 
bool isPalindromeRec(char str[], int s, int e)
{
    //Single character, return true
    if (s == e)
    {
       return true;
    }
    //If first and last characters do not match
    //Return false
    if (str[s] != str[e])
    {
       return false;
    }
    //If they are same, recursion for remaining 
    if (s < e+1)
    {
       return isPalindromeRec(str, s+1, e-1);
    }  
    //If it reaches end, return true
    return true;
}
 
bool isPalindrome(char str[])
{
   int n = strlen(str);
   //empty string is palindrome
   if (n == 0)
   {
     return true;
   }
   //Else, call recursive function
   return isPalindromeRec(str, 0, n-1);
}
 
// Main Function
int main()
{
    char str[] = "racecar";
    if (isPalindrome(str))
    {
      cout<<"Given input string is palindrome"<<endl;;
    }
    else
    {
       cout<<"Input string is not palindrome"<<endl;
    }
    return 0;
}

Try It

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions