Palindrome using Recursion

Problem Statement

In the “Recursive Palindrome Check” or “Palindrome using Recursion” 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 sequence 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 contains a string “s”.

Output Format

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

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.

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.