Recursive Palindrome Check  

Difficulty Level Easy
Frequently asked in Capgemini Factset Infosys MAQ o9 solutions Oracle Square
Palindrome String

Problem Statement  

In the “Recursive Palindrome Check” problem we have given a string “s”. We have to write a program to check if the given string is palindrome or not using recursion. A palindrome is a word, number, phrase, or other sequences of characters that reads the same backward as forward, such as madam or racecar.

Note: Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

Input Format  

The first and only one line containing a string “s”.

Output Format  

Print “Yes” if the given string is a palindrome otherwise print “No”.

Please click Like if you loved this article?

Constraints  

  • 1<=|s|<=10^6
  • s[i] must be a lower case alphabet

Example  

racecar
Yes

Explanation: Here if we read “racecar” from the left to right or from right to left then the meaning remains the same. So our string is a palindrome.

racing
No

Explanation: Here if we read “racing” from the left to right or from right to left then the meaning changed. So, in this case our string is not a palindrome.

Algorithm for Recursive Palindrome Check  

1. Call the function “palindrome_check” from the main body.

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

See also
Single Number

3. Else, compare the first and last characters and check them.

4. If both char are the same then apply recursion to the remaining sub-string.

5. Else return False;

Implementation  

C++ Program for Recursive Palindrome Check

#include <bits/stdc++.h>
using namespace std;

int palindrome_check(string s, int start, int end)
{
    if(end-start==1 || start==end)
    {
        return 1;
    }
    else
    {
        if(s[start]==s[end])
        {
            return palindrome_check(s,start+1,end-1); 
        }
        else
        {
            return 0;
        }
    }
}

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   if(palindrome_check(s, 0, n-1))
   {
       cout<<"Yes"<<endl;
   }
   else
   {
       cout<<"No"<<endl;
   }
   return 0;
}

Java Program for Recursive Palindrome Check

import java.util.Scanner;

class sum
{ 
        public static int palindrome_check(char [] s, int start, int end)
        {
            if(start==end || (end-start==1))
            {
                return 1;
            }
            else
            {
                if(s[start]==s[end])
                {
                    return palindrome_check(s,start+1,end-1);
                }
                else
                {
                    return 0;
                }
            }
        }
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                if(palindrome_check(a,0,n-1)==1)
                {
                    System.out.println("Yes");
                }
                else
                {
                    System.out.println("No");
                }
  } 
} 
abcdcba
Yes

Complexity Analysis for Recursive Palindrome Check  

Time Complexity

O(n) where n is the size of the string. Here we check the start and end of the string and update the values of start and end if char is the same at that position otherwise return 0.

Space Complexity

O(1) because we don’t create any auxiliary space here. Here we simply define one function and simply return the answer on the basis of the conditions.

Please click Like if you loved this article?