Palindrome string check using Recursion in C++

In this tutorial, we will learn how to check whether a String is a Palindrome or not using Recursion in C++.

A string is said to be Palindrome if the original string and its reverse is equal.

Let us see how this algorithm works.

Algorithm to check palindrome string using Recursion

1. Let s be the string that has to be checked for palindrome.
2. We define a recursive function recpal which takes 3 parameters: i for index, s for the string and n for the size of the string.
3. Then we check whether the index i is greater than or equal to the half of the size of the string.
4. If yes, it means we have checked upto half the size of the string from the beginning and from back side, hence it returns true.
5. Then we check if anytime the character at index [ i ] and [ n-1-i ] are not equal.
6. If yes, it means the string cannot be palindrome, hence it returns false.
7. then we call the function again now with the index i+1.
8. Define the main function.
9. Take input in test for the number of words the user wants to test for Palindrome.
10. Use a while loop for decreasing test case.
11. Take the word input in s from the user and call the function recpal with parameters 0, s and size of s.
12. The value returned by recpal will be stored in a boolean variable named flag.
13. Then we check whether the flag is true or false.
14. If true then the word is palindrome else it’s Not Palindrome.

For example:

Input:
2
GAURAV
MADAM

Output:
Not Palindrome
Palindrome

C++ Code: Palindrome string check

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

bool recpal(int i,string s, int n)
{
    if(i>=n/2)
        return true;

    if(s[i]!=s[n-1-i])
        return false;

    return (recpal(i+1,s,n));
}
      
int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        string s;
        cin>>s;
        bool flag=recpal(0,s,s.size());

         if(flag==true)
             cout<<"Palindrome"<<endl;

        else
            cout<<"Not Palindrome"<<endl;
    }
    

    return 0;
}

Input:
2
GAURAV
MADAM

Output:
Not Palindrome
Palindrome