C Program to Check whether a String is Palindrome or not using Recursion

This C program checks whether a given string is a palindrome or not using recursion.

Problem Statement

Write a C program that checks whether a given string is a palindrome or not using recursion. A palindrome is a string that reads the same forwards and backward. The program should use recursion to determine if the string is a palindrome and print an appropriate message indicating the result.

Example:

Input: Enter a string: radar

Output: The string is a palindrome.

Input: Enter a string: hello

Output: The string is not a palindrome.

Note:

• The program should handle both uppercase and lowercase letters.
• The program should not consider spaces, punctuation, or special characters when checking for a palindrome.
• The program should use recursion to solve the problem.

C Program to Check whether a String is Palindrome or not using Recursion

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isPalindrome(char str[], int start, int end)
{
    // Base case: if the start and end indices meet or cross each other,
    // the string is a palindrome
    if (start >= end) {
        return true;
    }
    
    // Recursive case: check if the characters at start and end indices
    // are equal, and recursively check the remaining substring
    if (str[start] == str[end]) {
        return isPalindrome(str, start + 1, end - 1);
    }
    
    // If the characters at start and end indices are not equal,
    // the string is not a palindrome
    return false;
}

int main()
{
    char str[100];
    
    printf("Enter a string: ");
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = '\0';  // remove trailing newline
    
    int len = strlen(str);
    
    if (isPalindrome(str, 0, len - 1)) {
        printf("The string is a palindrome.\n");
    } else {
        printf("The string is not a palindrome.\n");
    }
    
    return 0;
}

How it Works

1. The program prompts the user to enter a string.
2. The isPalindrome function is called with the input string, start index 0, and end index len - 1, where len is the length of the string.
3. The isPalindrome function checks the following conditions:
   • Base case: If the start index is greater than or equal to the end index, it means the recursion has reached the center of the string or crossed it. In this case, the function returns true, indicating that the string is a palindrome.
   • Recursive case: If the characters at the start and end indices are equal, the function makes a recursive call to itself with the start index incremented by 1 and the end index decremented by 1. This recursive call checks the remaining substring. If the characters at the updated indices are also equal, the function continues the recursion. If the characters are not equal at any point, the function returns false, indicating that the string is not a palindrome.
4. The main function receives the result from the isPalindrome function. If it is true, the program prints “The string is a palindrome.” If it is false, the program prints “The string is not a palindrome.”

The recursive approach breaks down the problem into smaller subproblems by comparing characters at the start and end indices. It eliminates the need for explicit loops and allows the program to check whether the string is a palindrome by considering smaller and smaller substrings. The recursion stops when the start and end indices meet or cross each other, indicating that the entire string has been checked.

Input / Output

Explanation: The user enters the string “radar”. The program calls the isPalindrome function with the string “radar”, start index 0, and end index 4 (length – 1).

The isPalindrome function checks if the characters at indices 0 and 4 (first and last characters) are equal, which they are (‘r’ and ‘r’). It then recursively calls itself with start index 1 and end index 3, continuing to check the substring “ada”.

Again, it checks if the characters at indices 1 and 3 are equal (‘a’ and ‘a’), which they are. It continues recursively with start index 2 and end index 2, checking the substring “d”.

Since there is only one character left, the function returns true. The main function receives true from isPalindrome and prints “The string is a palindrome.”

Explanation: The user enters the string “hello”. The program calls the isPalindrome function with the string “hello”, start index 0, and end index 4 (length – 1).

The isPalindrome function checks if the characters at indices 0 and 4 (first and last characters) are equal, which they are not (‘h’ and ‘o’). It immediately returns false since the string is not a palindrome.

The main function receives false from isPalindrome and prints “The string is not a palindrome.”