Check String Is Palindrome Or Not In Java Using Recursion

Identifying palindromes is a common task in programming, often used to test understanding of string manipulation and algorithmic concepts. In this article, you will learn how to determine if a given string is a palindrome in Java using a recursive approach, offering a concise and elegant solution.

Problem Statement

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization. The challenge is to programmatically check if a string meets this definition, which is crucial in various text processing and data validation scenarios.

Example

Consider the word "madam". Reading it forwards: m-a-d-a-m Reading it backwards: m-a-d-a-m Since both readings are identical, "madam" is a palindrome.

Background & Knowledge Prerequisites

To effectively follow this article, readers should have a basic understanding of:

• Java Fundamentals: Variables, data types, conditional statements (if/else).
• String Manipulation: Accessing characters by index, string length.
• Recursion: The concept of a function calling itself, including base cases and recursive steps.

Use Cases or Case Studies

Checking for palindromes has several practical applications:

• Data Validation: Ensuring user input, such as special passphrases or codes, adheres to a palindrome pattern.
• Text Processing and Analysis: Identifying palindromic words or sentences in large texts for linguistic studies or puzzles.
• Algorithmic Challenges: Often used in coding interviews and competitive programming as a basic problem to assess recursive thinking.
• Game Development: Creating word games or puzzles where players need to identify or construct palindromes.
• Bioinformatics: Analyzing DNA or RNA sequences for palindromic repeats, which can have biological significance.

Solution Approaches

We will focus on a recursive method for checking if a string is a palindrome.

Recursive Palindrome Check

This approach leverages recursion by comparing characters from both ends of the string and then recursively checking the substring between them.

// PalindromeChecker
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {

    /**
     * Checks if a given string is a palindrome using recursion.
     * Ignores non-alphanumeric characters and case.
     * @param s The input string.
     * @return true if the string is a palindrome, false otherwise.
     */
    public static boolean isPalindromeRecursive(String s) {
        // Step 1: Handle null or empty string as a palindrome
        if (s == null || s.length() == 0 || s.length() == 1) {
            return true;
        }

        // Step 2: Normalize the string: remove non-alphanumeric and convert to lowercase
        String normalizedString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

        // Step 3: Call the helper function for recursive check
        return checkPalindrome(normalizedString, 0, normalizedString.length() - 1);
    }

    /**
     * Helper recursive function to check for palindrome.
     * @param s The normalized string.
     * @param left The left pointer index.
     * @param right The right pointer index.
     * @return true if the substring from left to right is a palindrome, false otherwise.
     */
    private static boolean checkPalindrome(String s, int left, int right) {
        // Base Case 1: If left pointer crosses or meets the right pointer, it's a palindrome
        if (left >= right) {
            return true;
        }

        // Step 4: Compare characters at current left and right pointers
        if (s.charAt(left) != s.charAt(right)) {
            return false; // Characters don't match, not a palindrome
        }

        // Step 5: If characters match, recursively check the inner substring
        return checkPalindrome(s, left + 1, right - 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Prompt user for input string
        System.out.print("Enter a string to check if it's a palindrome: ");
        String input = scanner.nextLine();

        // Step 2: Call the palindrome checker function
        boolean result = isPalindromeRecursive(input);

        // Step 3: Print the result
        if (result) {
            System.out.println("'" + input + "' is a palindrome.");
        } else {
            System.out.println("'" + input + "' is NOT a palindrome.");
        }

        // Test with more examples
        System.out.println("\\n--- Testing with pre-defined examples ---");
        System.out.println("'Madam' is a palindrome: " + isPalindromeRecursive("Madam"));          // True
        System.out.println("'Racecar' is a palindrome: " + isPalindromeRecursive("Racecar"));      // True
        System.out.println("'A man, a plan, a canal: Panama' is a palindrome: " + isPalindromeRecursive("A man, a plan, a canal: Panama")); // True
        System.out.println("'hello' is a palindrome: " + isPalindromeRecursive("hello"));          // False
        System.out.println("'' (empty string) is a palindrome: " + isPalindromeRecursive(""));     // True
        System.out.println("'a' (single char) is a palindrome: " + isPalindromeRecursive("a"));    // True
        System.out.println("'ab' is a palindrome: " + isPalindromeRecursive("ab"));                // False

        scanner.close();
    }
}

Run

Sample output:

Enter a string to check if it's a palindrome: level
'level' is a palindrome.

--- Testing with pre-defined examples ---
'Madam' is a palindrome: true
'Racecar' is a palindrome: true
'A man, a plan, a canal: Panama' is a palindrome: true
'hello' is a palindrome: false
'' (empty string) is a palindrome: true
'a' (single char) is a palindrome: true
'ab' is a palindrome: false

Stepwise Explanation:

1. isPalindromeRecursive(String s) Function:

• This is the public entry point. It first handles edge cases like null, empty, or single-character strings, which are always palindromes.
• It then normalizes the input string by removing all non-alphanumeric characters and converting it to lowercase. This ensures the palindrome check is case-insensitive and ignores punctuation/spaces.
• Finally, it calls a private helper function, checkPalindrome, passing the normalized string and initial left (0) and right (length - 1) pointers.

1. checkPalindrome(String s, int left, int right) Helper Function:

• Base Case 1 (left >= right): If the left pointer has crossed or met the right pointer, it means all characters have been successfully compared, or it's a single-character/empty substring. In this case, the substring is a palindrome, and true is returned. This is crucial to stop the recursion.
• Character Comparison: It compares the character at the left index with the character at the right index.
• Mismatch (s.charAt(left) != s.charAt(right)): If the characters do not match, the string is not a palindrome, and false is immediately returned.
• Recursive Call: If the characters match, the function recursively calls itself with left + 1 and right - 1. This effectively "shrinks" the string from both ends, moving towards the center, until a base case is hit or a mismatch is found.

1. main Method:

• Prompts the user to enter a string.
• Calls isPalindromeRecursive with the user's input.
• Prints whether the input string is a palindrome or not.
• Includes additional hardcoded examples to demonstrate the function's behavior with various valid and invalid palindromes.

Conclusion

Recursion offers an elegant and often more readable way to solve problems like palindrome checking, especially when the problem can be broken down into smaller, self-similar subproblems. By establishing clear base cases and recursive steps, we can effectively determine if a string reads the same forwards and backward, even when accounting for case and non-alphanumeric characters.

Summary

• A palindrome reads the same forwards and backward.
• The recursive approach compares characters from the ends of the string.
• Normalization (removing non-alphanumeric characters, converting to lowercase) is important for robust checks.
• Base cases for recursion include empty strings, single-character strings, or when pointers cross/meet.
• The recursive step involves calling the function on the inner substring after matching outer characters.