Given a string, write a recursive function that checks if the given string is a palindrome, else, not a palindrome.
Examples:
Input : malayalam
Output : Yes
Reverse of malayalam is also
malayalam.
Input : max
Output : No
Reverse of max is not max.
The idea of a recursive function is simple:
- If there is only one character in string
return true. - Else compare first and last characters
and recur for remaining substring.
Below is the implementation of the above idea:
#include <bits/stdc++.h>
using namespace std;
// A recursive function that
// check a str[s..e] is
// palindrome or not.
bool isPalRec(char str[],
int s, int e)
{
// If there is only one character
if (s == e)
return true;
// If first and last
// characters do not match
if (str[s] != str[e])
return false;
// If there are more than
// two characters, check if
// middle substring is also
// palindrome or not.
if (s < e + 1)
return isPalRec(str, s + 1, e - 1);
return true;
}
bool isPalindrome(char str[])
{
int n = strlen(str);
// An empty string is
// considered as palindrome
if (n == 0)
return true;
return isPalRec(str, 0, n - 1);
}
// Driver Code
int main()
{
char str[] = "geeg";
if (isPalindrome(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Output
Yes
// Time Complexity: O(n)
// Auxiliary Space: O(n)