Check if string is palindrome or not using recursion in C

Today we are going to solve a very commonly asked interview question using one the core topic's of programming i.e. Recursion. Mostly this is asked as a follow-up question by the interviewer.

The problem is to check whether the given string in a palindrome or not.

A palindromic string is a string that remains the same when its characters are reversed.

Example:

Explanation : Reversing "ABCCAB" results in "BACCBA" and both are not same so it is a non - palindromic string.

Recursive Approach:

The idea is to take 2 pointers pointing at the first character and the other at the end character and check if both characters are equal until we reach the middle of the string. If a mismatch happens between any comparison we can then say that the given string is not a palindrome.

As this is a recursive solution we know there are 3 parts of a recursive solution to a problem:

1. Base case
2. Work until you reach the base case
3. Recursive calls

Since we are taking two pointers one for pointing at the start and another for pointing at the end, they are to be increased and decreased respectively after every check until both the pointer's reach the middle of the string, so that will be our base case. 

If start pointer gets greater than or equal to the end pointer that means we have reached the middle of the string and if we have successfully reached there that means all the conditions have passed and the given string is a palindrome.
And our work is to check if at the character at the start position and end position same or not and continue calling the function until we reach the middle of the string or a mismatch happens with the pair.

Code:

//C++ Code
#include <iostream>
#include<string>
using namespace std;
bool isPalindrome(string str,int start,int end)
{
    if(start >= end) //base case
    return true;
    else{
        //if mismatch happens false will be returned else true
        return ((str[start] == str[end]) && isPalindrome(str,start+1,end-1));
    }
}
int main()
{
    int length = 5;
    string str = "ABCBA";
    bool ans = isPalindrome(str,0,length-1);
    if(ans == true)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    return 0;
}

Explanation: Our function isPalindrome()  is made up of 3 parameters a user given string, and indexes of starting and ending point of the string i.e. start = 0, and end = length of the string-1(0-th based index).

We know our string is a palindrome if the string remains same after reversing it, so we are taking advantage of this known fact. We are trying to check if the start index == end index. If this isn't true then there is no way that it can be palindrome because if we want to reverse the string the first element will become the last element, the second element will become the second last element and so on, so if we check that first is equal to the last element or not, and further increase the start index and decrease the end index till both index are not met. If there are no mismatches that means if we reverse the string the answer will be same as the current one i.e. the property of a palindromic string. 

Let's take an example to understand, suppose the given string = "A", the length = 1 so the start index = 0 and end index = string length - 1 = 0. So both start and end index match that is the base condition since, if both are pointing at a same place if we reverse it, that will be same every time. So, the answer true is returned.

Now let's discuss about the example given in the code i.e. string = "ABCBA", now start index = 0 and end index = length -1 = 4. So, when the function is called from the main, the first thing happens is that the base condition is checked, here the base case is false since start index <  end index, so we move further in the else part where we are simultaneously checking if string[start] == string[end] or not i.e. here if string[0] == string[4] this is true since both the first and last element value is  'A'. Then we make a call again with increasing the start index and decreasing the end index i.e. isPalindrome(string, start+1, end-1), after this call now the function call is happening with parameter string, start = 1, and end = 3. So first the base case is checked, that is false since 1 < 4 then we go to the else part if(string[1] == string[3]). It is true since element at string[1] is 'B' and same is at string[3] so we again call the function with the modified values that is isPalindrome(string, start+1, end-1) i.e.,  start = 3 and end = 3. So, again there is function call, now in this case start >= end is true that means they have reached the mid way and there are no mismatches till now that means the string is a palindrome.

When there is a case where a mismatch happens we are returned false with the help logical AND operator used in the else part of the code. So if both the conditions i.e. if( string[start] == string[end]) is false then no further calls will happen because  this disqualifies to satisfy the AND operator conditions because the logical AND operator (&&) returns true only if both operands are true and returns false otherwise. If there is found 1 false condition then there are no further checking, it is taken as false.

Complexity Analysis:

The time complexity of the above discussed recursive method is O(n), where n is the length of the input string. And O(n) implicit space for the call stack.
You can solve this question in O(n) time complexity and O(1) space complexity with the iterative method.