17.7. Recursive String Reversal¶

Problem: Given a string, how can we produce its characters in reverse order? For example, reversing "abc" should give us "cba". For this example, use short ASCII strings whose reference values are not null. The empty string is a valid input.

Think about a smaller version of this problem. If we already knew how to reverse "bc", what would we need to do to reverse "abc"? We could append the first character, 'a', to the result of reversing "bc". Notice that we need both parts: solving the sub-problem is not enough unless we use its result.

Given the above problem description, identify the base cases and the recursive case. Now, try to write a method called reverse that takes a String argument and returns with a reference to the reversed string.

Don't read beyond this point until you've attempted to write the recursive reverse method.

Sample Solution

The following method is included in the cs1302-recursion bundle:

Bundle

Execute the command below to download and extract the files:

bundle1302 recursion

- downloading cs1302-recursion bundle...
- verifying integrity of downloaded files using sha256sum...
- extracting downloaded archive...
- removing intermediate files...
subdirectory cs1302-recursion successfully created

public static String reverse(String str) {
    if (str.length() <= 1) {
        return str;
    } else {
        return reverse(str.substring(1)) + str.charAt(0);
    } // if
} // reverse

A string with zero or one character is already in reverse order, so the base case returns with the original reference. Otherwise, we reverse the substring after the first character, then append that first character. The method does not always create a new string object.

Note

Java's charAt and the substring indexes used here operate on UTF-16 code units. Reversing those units works for our ASCII examples, but it does not preserve all Unicode characters. Keep that limitation in mind when choosing inputs for this example.

Sample Recursion Tree

Here is a sample recursion tree for reverse("abc"):

reverse("abc")
     |
reverse("bc") + 'a'
     |
reverse("c") + 'b'
     |
    "c"

The concatenations are shown to the side, just as the multiplications were in the factorial example. They are performed as the recursive method calls complete normally:

reverse("c")   completes with a reference to "c"
reverse("bc")  combines "c" + 'b', producing "cb"
reverse("abc") combines "cb" + 'a', producing "cba"

Sample Call Stack

Immediately after calling reverse("c"), three calls to reverse are active. Reading from the oldest frame to the newest, we have:

method call       str       work remaining
reverse("abc")    "abc"     append 'a' to the recursive result
reverse("bc")     "bc"      append 'b' to the recursive result
reverse("c")      "c"       supply the base-case result

The newest call completes first. Its result is used by the call for "bc", whose result is then used by the call for "abc". Each call has its own parameter variable, even though we use the name str in every frame.

Test Yourself

What happens if we use str.length() == 1 as the only base case and call reverse("")?
What would happen if the recursive case used str.charAt(0) + reverse(str.substring(1)) instead?
Suppose we store the recursive result in a local variable, but then use return str; without using that variable. Does calling the method recursively guarantee that the final result is reversed?