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

 


Next > < Prev
Scroll to Top