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

Reversing a string means writing its characters in the opposite order, so "hello" becomes "olleh". This note does it with a recursive method of our own, reverseText(), which calls itself and uses only the String methods length(), charAt() and substring().

Definition

The reverse of a string is obtained by taking its characters from the last to the first. For example:

• reverse of hello is olleh
• reverse of I love Java is avaJ evol I

The recursive idea: the reverse of a string is the reverse of everything except its first character, followed by the first character. So the reverse of "hello" is the reverse of "ello" followed by 'h'. A string with 0 or 1 characters is its own reverse, and this is the base case.

Algorithm

1. In main, create an object ob of class RevString and call accept() to read a whole line into str (with nextLine(), so spaces are kept).
2. Call reverseText(str) and store the result in rev.
   • Base case: if s.length() <= 1, return s.
   • Recursive case: return reverseText(s.substring(1)) + s.charAt(0).
   • s.substring(1) is the string without its first character, so each call works on a string one character shorter.
3. Call display() to print the original and the reversed string. Square brackets are printed around each so that leading and trailing spaces can be seen.

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

• Empty string: if the user just presses Enter, str 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. A trailing space moves to the front: "I love Java " becomes " avaJ evol I".

Program

accept() reads the string, reverseText() is the recursive method, and display() prints the result.

import java.util.*;

/** class RevString: reverses a string using recursion. */
class RevString
{
    String str;     // string entered by the user
    String rev;     // reverse of str

    /** Default constructor: initialises the data members. */
    RevString()
    {
        str = "";
        rev = "";
    }

    /** Reads a line of text (spaces allowed) from the user. */
    void accept()
    {
        Scanner sc = new Scanner(System.in);    // Scanner object for input
        System.out.print("Enter a string: ");
        str = sc.nextLine();                    // nextLine() so that spaces are kept
    }

    /** Recursive method: reverses a string.
        Base case: a string of length 0 or 1 is its own reverse.
        Recursive case: reverse of the string without its first character,
        followed by the first character.
        @param s the string to reverse
        @return the reversed string */
    String reverseText(String s)
    {
        if (s.length() <= 1)
            return s;                                       // base case
        return reverseText(s.substring(1)) + s.charAt(0);   // recursive case
    }

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

    /** main: creates the object and calls the methods. */
    public static void main(String args[])
    {
        RevString ob = new RevString();     // object of the class
        ob.accept();
        ob.rev = ob.reverseText(ob.str);
        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. The calls go down until the string has one character, then the values come back up.

rev becomes olleh, so the program prints Reversed string = [olleh].

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."
3. Reverse a number "Write a program to reverse a number using a recursive method."