# C Program for Palindrome Check using Recursion

• Write a C program to check if a string is palindrome or not using recursion.
• Algorithm to check palindrome string using recursion.

A string is palindrome, if string remains same after reversing sequence of it's character. For example, "tenet" is a palindrome string whereas "mango" is not a palindrome string.
We can check whether a string is palindrome or not using recursion by breaking this problem into a smaller problem.

Algorithm to check a string is palindrome or not using recursion

Let inputString is a string (character array) of length N and leftIndex and rightIndex are two integer variable.
• Initialize leftIndex and rightIndex to index of first character and last character of string respectively(leftIndex = 0; and rightIndex = N-1;)
• We will first check whether leftmost character(inputString[leftIndex]) is equal to rightmost character(inputString[rightIndex]).
• If equal, then we recursively perform palindrome check on sub string form index leftIndex+1 to rightIndex-1. if sub string(from inputString[leftIndex+1] to inputString[rightIndex-1]) is palindrome, then whole inputString is also palindrome, otherwise not a palindrome string.
• If not equal, then inputString is not a palindrome string.
• if(inputString[leftIndex] == inputString[rightIndex]) then isPalindrome(inputString, leftIndex+1, rightIndex-1) else "Not a Palindrome"
• Recursion will terminate, if leftIndex >= rightIndex.(when size of the sub-string is less than or equal to 1)

## C program for palindrome check using recursion

In below program, we first take a string as input from user and stores it in a character array named 'inputString'. Here, we are using a user defined recursive function named "isPalindrome" which checks whether a substring of string "inputString" from index leftIndex to rightIndex is palindrome or not. We call this function inside main function(at line number 17) by passing 0 and strlen(inputString)-1 as leftIndex and rightIndex of inputString to check whether inputString is palindrome or not.

Suppose out input string is "madam". To check whether input string is palindrome or not we will call isPalindrome function with following parameters
isPalindrome(inputString, 0, 4). As first and last character or input string are same, isPalindrome will recursively call itself to check whether the sub-string excluding the first and last character("ada") is palindrome or not and so on. Function isPalindrome will repeat this process unless length of sub-string is greater than one or first and last characters are unequal.

```/*
* C Program to check given string is palindrome or not
* using recursion
*/
#include <stdio.h>
#include <conio.h>
#include <string.h>

int isPalindrome(char *inputString, int leftIndex, int rightIndex);

int main(){
char inputString;
printf("Enter a string for palindrome check\n");
scanf("%s", inputString);

if(isPalindrome(inputString, 0, strlen(inputString) - 1)){
printf("%s is a Palindrome \n", inputString);
} else {
printf("%s is not a Palindrome \n", inputString);
}

getch();
return 0;
}

/*
* Function to check whether a string is palindrome or not
*/
int isPalindrome(char *inputString, int leftIndex, int rightIndex){
/* Input Validation */
if(NULL == inputString || leftIndex < 0 || rightIndex < 0){
printf("Invalid Input");
return 0;
}
/* Recursion termination condition */
if(leftIndex >= rightIndex)
return 1;
if(inputString[leftIndex] == inputString[rightIndex]){
return isPalindrome(inputString, leftIndex + 1, rightIndex - 1);
}
return 0;
}
```

Program Output
```Enter a string for palindrome check
```Enter a string for palindrome check