ISC Practicals and Theory - Palindrome String (Recursive Technique)

A palindrome string is a word that reads the same from left to right and from right to left. This program decides whether a word is a palindrome using recursion: the method isPalin() calls itself on a smaller string until it reaches a case it can answer directly.

Definition

A string is a palindrome if its first character equals its last, its second equals its second last, and so on up to the middle.

• madam is a palindrome: m=m, a=a, and d is left alone in the middle.
• computer is not a palindrome: its first character c differs from its last character r.
• A string of length 0 or 1 is always a palindrome. In this program the base case n <= 1 returns true, so a one-character word such as a is reported as a palindrome (checked by running the program).

This program ignores the difference between capital and small letters, so Madam is accepted: the word is converted with toLowerCase() before it is tested. It reads a single word with next(), so it stops at the first space (for "nurses run" only nurses is tested), and spaces and punctuation are not handled. An empty input cannot be tested: next() finds no word to read and the program stops with a NoSuchElementException.

Algorithm

1. accept() reads a word, converts it to lower case, stores it in str and its length in len.
2. display() calls isPalin(str).
3. isPalin(s) works on the string s:
   • Find n, the length of s.
   • Base case: if n <= 1, return true.
   • If the first character s.charAt(0) and the last character s.charAt(n - 1) are different, return false.
   • Recursive case: otherwise return isPalin(s.substring(1, n - 1)), that is the same question for the string without its first and last characters.
4. display() prints "is a Palindrome" if true came back, otherwise "is not a Palindrome".

Program

The class Palindrome has two data members. accept() takes the input, isPalin() is the recursive method and display() prints the result; main creates the object and calls them.

import java.util.Scanner;

/* Class Palindrome checks, using recursion, whether a word reads the same
   forwards and backwards. Upper and lower case letters are treated as equal. */
public class Palindrome
{
    String str;   // stores the word entered by the user (in lower case)
    int len;      // stores the number of characters in the word

    /* Default constructor: initialises the data members */
    Palindrome()
    {
        str = "";
        len = 0;
    }

    /* Reads one word from the user, converts it to lower case so that
       'Madam' and 'madam' are treated alike, and stores its length */
    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a word: ");
        String w = sc.next();      // word typed by the user
        str = w.toLowerCase();     // case is ignored while comparing
        len = str.length();
    }

    /* Recursive method. Parameter s: the part of the word still to be checked.
       Returns true if s is a palindrome, otherwise false. */
    boolean isPalin(String s)
    {
        int n = s.length();        // length of the string being checked
        if (n <= 1)                // base case: empty or single character
            return true;
        if (s.charAt(0) != s.charAt(n - 1))   // first and last characters differ
            return false;
        return isPalin(s.substring(1, n - 1)); // recursive case: drop both ends
    }

    /* Calls isPalin() on the stored word and prints the result */
    void display()
    {
        if (isPalin(str))
            System.out.println(str + " is a Palindrome");
        else
            System.out.println(str + " is not a Palindrome");
    }

    /* main creates the object and calls the methods */
    public static void main(String args[])
    {
        Palindrome ob = new Palindrome();   // object of class Palindrome
        ob.accept();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a word: Madam
madam is a Palindrome

Enter a word: Computer
computer is not a Palindrome

Enter a word: a
a is a Palindrome

Dry run

Input Madam. After conversion str = madam. The calls go down until the base case, then the answers come back up.

display() receives true and prints madam is a Palindrome, the same as the real run above.

Variations

1. Palindrome sentence "Write a program to check whether a sentence is a palindrome, ignoring spaces and punctuation."
2. Reverse a string "Write a program to reverse a string using recursive technique."