Check palindrome using Recursion in C++

By ARYA CHANDRAKAR

In this tutorial, we learn how to check whether a given string is palindrome or not using recursion in C++ language. Time complexity: O(n), Auxiliary space: O(n).

Examples:

Input: racecar

Output: true

The reverse of a racecar is a racecar.

 

Input: coder

Output: false

Reverse of coder is redoc.

Approach:

1) If there is only one character in the string return true.

2) Else compare the first and last characters and recur for the remaining substring.

Code:

#include<bits/stdc++.h>
using namespace std;
// A recursive function that
// check a string is
// palindrome or not.
bool helper(char input[],int size)
{
    //if string is empty
    if(size<=0)
    {
        return true;
    }
    //checks first and last character of string 
    else if (input[0]!=input[size])
    {
        return false;
    }

       return helper(input+1,size-2);
    
}
bool checkPalindrome(char input[]) {
    
    int size=strlen(input);
    if(size==1)
        return true;
    
    return helper(input,size-1);
}
 
// Driver Code
int main()
{
    char str[] = "racecar";
 
    if (checkPalindrome(str))
    cout << "true";
    else
    cout << "false";
 
    return 0;
}

Output: true

Time Complexity: O(n)

Auxiliary Space: O(n)