ISC Practicals and Theory - Reverse a String (Recursive Technique) (OOP)

This version reverses a string, for example "hello" to "olleh", with a recursive method, written as a class where the string is passed to a parameterised constructor and each method does one job. Only length(), charAt() and substring() are used, together with the method's own recursion.

Definition

The reverse of a string is its characters in the opposite order. The reverse of a string is the reverse of all but its first character, followed by the first character. A string of length 0 or 1 is its own reverse (the base case).

Algorithm

1. In main, read the line into s using nextLine() (spaces are kept) and create the object with new StringReverser(s). The constructor stores it in text and sets reversed to "".
2. Call process(), which calls reverse(text) and keeps the result in reversed.
   • Base case: if s.length() <= 1, return s.
   • Recursive case: return reverse(s.substring(1)) + s.charAt(0).
3. Call display() to print the original and the reversed string inside square brackets, so that spaces at the ends are visible.

Two cases worth knowing, both checked by running the program:

• Empty string: if the user just presses Enter, text is empty, the base case returns it unchanged and the program prints Original string = [] and Reversed string = []. There is no separate message.
• Spaces: spaces are ordinary characters, so they are reversed along with the letters. For the input " ab c" (two spaces at the start) the output is [c ba ], with the two spaces now at the end.

Program

The constructor stores the string, reverse() is the recursive method, process() calls it and saves the answer, and display() prints.

import java.util.*;

/** class StringReverser: stores a string and reverses it using recursion. */
class StringReverser
{
    private String text;        // string to be reversed
    private String reversed;    // reversed form of text

    /** Parameterised constructor: stores the string and sets reversed to empty.
        @param s the string to be reversed */
    StringReverser(String s)
    {
        text = s;
        reversed = "";
    }

    /** Recursive method: reverses a string.
        @param s the part of the string still to be reversed
        @return the reverse of s */
    String reverse(String s)
    {
        if (s.length() <= 1)
            return s;                                   // base case: empty or one character
        return reverse(s.substring(1)) + s.charAt(0);   // recursive case
    }

    /** Calls reverse() for the stored string and keeps the result in reversed. */
    void process()
    {
        reversed = reverse(text);
    }

    /** Displays the original and the reversed string. */
    void display()
    {
        System.out.println("Original string = [" + text + "]");
        System.out.println("Reversed string = [" + reversed + "]");
    }

    /** main: reads the string, creates the object and calls the methods. */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);        // Scanner object for input
        System.out.print("Enter a string: ");
        String s = sc.nextLine();                   // line typed by the user, spaces kept
        StringReverser ob = new StringReverser(s);  // object of the class
        ob.process();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a string: hello
Original string = [hello]
Reversed string = [olleh]

Enter a string: I love Java
Original string = [I love Java]
Reversed string = [avaJ evol I]

Enter a string: a
Original string = [a]
Reversed string = [a]

Dry run

Input hello: process() calls reverse("hello"). The calls go down to a one-character string and the values come back up.

reversed becomes olleh, so the program prints Reversed string = [olleh], the same as the real run above.

Variations

1. Palindrome String "Write a program to check whether a string is a palindrome using a recursive method."
2. Count vowels "Write a program to count the vowels in a string using a recursive method."