Here is a C program to check if a string is palindrome or not 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.
- 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.
#include <stdio.h>
#include <string.h>
int isPalindrome(char *inputString, int leftIndex, int rightIndex);
int main(){
char inputString[100];
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);
}
return 0;
}
int isPalindrome(char *inputString, int leftIndex, int rightIndex){
if(NULL == inputString || leftIndex < 0 || rightIndex < 0){
printf("Invalid Input");
return 0;
}
if(leftIndex >= rightIndex)
return 1;
if(inputString[leftIndex] == inputString[rightIndex]){
return isPalindrome(inputString, leftIndex + 1, rightIndex - 1);
}
return 0;
}
Output
Enter a string for palindrome check MADAM MADAM is a Palindrome
Enter a string for palindrome check TECHCRASHCOURSE TECHCRASHCOURSE is not a Palindrome
Related Topics
