Java, Java, Java: Recursive String Methods

15. Recursive Problem Solving

15.3. Recursive String Methods

Remember that a recursive method is a method that calls itself. Like re- cursive definitions, recursive methods are designed around the divide- and-conquer and self-similarity principles. Defining a recursive method involves a similar analysis to the one we used in designing recursive defi- nitions. We identify a self-similar subproblem of the original problem plus one or more limiting cases.

The idea of a method calling itself seems a bit strange at first. It’s per-

haps best understood in terms of a clone or a copy. When a method calls

itself, it really calls a copy of itself, one that has a slightly different internal

Figure 12.4: Write a recursive def- inition for this pattern.

How can a method call itself?

Head-and-tail algorithm

state. Usually the difference in state is the result of a difference in the invoked method’s parameters.

Printing a String

To illustrate the concept of a recursive method, let’s define a recursive method for printing a string. This is not intended to be a practical method—we already have the println() method for printing strings. But pretend for a moment that you only have a version of println() that works for characters, and your task is to write a version that can be used to print an entire string of characters.

A little terminology will help us describe the algorithm. Let’s call the first letter of a string the head of the string, and let’s refer to all the remain- ing letters in the string as the tail of the string. Then the problem of print- ing a string can be solved using a head-and-tail algorithm, which consists of two parts: printing the head of the string and recursively printing its tail. The limiting case here is when a string has no characters in it. It’s trivial to print the empty string—there is nothing to print! This leads to the method definition shown in Figure 12.5.

Figure 12.5: The recursive printString() method.

The base case here provides a limit and bounds the recursion when the length of s is 0—that is, when the string is empty. The recursive case solves the problem of printing s by solving the smaller, self-similar problem of printing a substring of s. Note that the recursive case makes progress to- ward the limit. On each recursion, the tail will get smaller and smaller until it becomes the empty string.

Recursive call

Let’s now revisit the notion of a method calling itself. Obviously this is what happens in the recursive case, but what does it mean—what actions does this lead to in the program? Each recursive call to a method is really a call to a copy of that method, and each copy has a slightly different internal state. We can define printString()’s internal state completely in terms

of its recursion parameter, s, which is the string that’s being printed. A recursion parameter is a parameter whose value is used to control the progress of the recursion. In this case, if s differs in each copy, then so will s.substring(1) and s.charAt(0).

Figure 12.6 illustrates the sequence of recursive method calls and the output that results when printString("hello") is invoked. Each box

Figure 12.6: A recursive method

printString("hello")

Output Produced

call invokes a copy of the method, each with a slightly different in- ternal state. As this is done re- peatedly, a stack of method calls is created.

represents a separate instance of the printString() method, with its

own internal state. In this illustration, its state is represented by its pa-Self-similar instances

rameter, s. Because each instance has a different parameter, behaviors differ slightly. Each box shows the character that will be printed by that

instance (s.charAt(0)), and the string that will be passed on to the next instance (s.substring(1)).

Progress toward the bound

The arrows represent the method calls and returns. Note that the first return executed is the one in the base case. Each instance of the method must wait for the instance it called to return before it can return. That’s why the instances “pile up” in a cascade-like structure. The arrowless lines trace the order in which the output is produced.

Each instance of printString() is similar to the next in that each will print one character and then pass on a substring, but each performs its duties on a different string. Note how the string, the recursion param- eter in this case, gets smaller in each instance of printString(). This represents progress toward the method’s base case s.length() == 0. When the empty string is passed as an argument, the recursion will stop. If the method does not make progress toward its bound in this way, the result will be an infinite recursion.

Self-similarity

Note also the order in which things are done in this method. First s.charAt(0) is printed, and then s.substring(1) is passed to printString() in the recursion. This is a typical structure for a head- and-tail algorithm. What makes this work is that the tail is a smaller, self-similar version of the original structure.

SELF-STUDY EXERCISE

EXERCISE 12.7What would be printed by the following version of the

printString2() method, if it is called with printString2("hello")?

Printing the String Backward

What do you suppose would happen if we reversed the order of the state- ments in the printString() method? That is, what if the recursive call came before s.charAt(0) is printed, as in the following method:

As its name suggests, this method will print the string in reverse order.The trace in Figure 12.7 shows how this works.Before printReverse("hello") can print h, it calls printReverse("ello") and must wait for that call to complete its execution and return. But printReverse("ello") calls printReverse("llo") and so must wait for that call to complete its execution and return.

This process continues until printReverse("") is called. While the base case is executing, the other five instances of printReverse() must each wait for the instance that they called to complete its execution. It is only after the base case returns, that printReverse("o") can print its first character and return. So the letter o will be printed first. After printReverse("o") has returned, then printReverse("lo") can print its first character. So the letter l will be printed next, and so on, until the original call to printReverse("hello") is completed and returns. Thus, the string will be printed in reverse order.

Note that the method call and return structure in this example follows a

last-in–first-out (LIFO) protocol. That is, the last method called is alwaysLast-in–first-out protocol

Figure 12.7: A trace of print- Reverse(s), which prints its string argument in reverse order.

printReverse("hello")

the first method to return. This is the protocol used by all method calls, recursive or otherwise.

Method call stack

For example, compare the order in which things happen in Figure 12.7 with the method stack trace in Figure 10.12. The only real difference between the two figures is that here the method stack is represented as growing downward, whereas in Figure 10.12 it grows upward. As each method call is made, a representation of the method call is placed on the method call stack. When a method returns, its block is removed from the top of the stack. The only difference between recursive and nonrecursive method calls is that recursive methods call instances of the same method definition. Of course, as we’ve seen, the instances are all slightly different from each other.

SELF-STUDY EXERCISES

EXERCISE 12.8 Write a recursive method called countDown() that takes a single int parameter, N 0, and prints a countdown, such as “5, 4, 3, 2, 1, blastoff.” In this case, the method would be called with countDown(5).

EXERCISE 12.9 Revise the method in the previous exercise so that when it’s called with countDown(10), it will print “10 8 6 4 2 blastoff”;

if it’s called with countDown(9), it prints “9 7 5 3 1 blastoff.”

Counting Characters in a String

Suppose you’re writing an encryption program and you need to count the

frequencies of the letters of the alphabet. Let’s write a recursive methodProblem statement

for this task.

This method will have two parameters: a String to store the string that will be processed and a char to store the target character—the one we want to count. The method should return an int, representing the number of occurrences of the target character in the string:

Here again our analysis must identify a recursive step that breaks the problem into smaller, self-similar versions of itself, plus a base case or limiting case that defines the end of the recursive process. Because the empty string will contain no target characters, we can use it as our base case. So, if it is passed the empty string, countChar() should just return 0 as its result.

For the recursive case, we can divide the string into its head and tail. If the head is the target character, then the number of occurrences in the string is (1 + the number of occurrences in its tail). If the head of the string is not the target character, then the number of occurrences is (0 + the number of occurrences in its tail). Of course, we’ll use recursion to calculate the number of occurrences in the tail.

This analysis leads to the recursive method shown in Figure 12.8. Note that for both recursive cases the same recursive call is used. In both cases we pass the tail of the original string, plus the target character. Note also how the return statement is evaluated:

Base case

Recursive case

Before the method can return a value, it must receive the result of call-

ing countChar(s.substring(1),ch) and add it to 1. Only then canEvaluation order is crucial

s t r

Figure 12.8: The recursive countChar() method.

a result be returned to the calling method. This leads to the following evaluation sequence for countChar("dad",’d’):

In this way, the final result of calling countChar("dad",’d’) is built up recursively by adding together the partial results from each separate instance of countChar(). The evaluation process is shown graphically in Figure 12.9.

Figure12.9:Atraceof countChar("dad",’d’), which returns the value 2.

countChar("dad",'d');Result

1+ 0 + 1 + 0 = 2

0 + 1 + 0

1 + 0

Base case

SELF-STUDY EXERCISE

EXERCISE 12.10 Here’s a numerical problem. Write a recursive method to compute the sum of 1 to N, given N as a parameter.

Translating a String

A widely used string-processing task is to convert one string into another string by replacing one character with a substitute throughout the string. For example, suppose we want to convert a Unix path name, which uses the forward slash “/” to separate one part of the path from another, into a

Windows path name, which uses the backslash character “ ” as a separa-Problem statement

tor. For example, we want a method that can translate the following two strings into one another:

Thus, we want a method that takes three parameters: a String, on

which the conversion will be performed, and two char variables, the first Method design

being the original character in the string and the second being its substi- tute. The precondition for this method is simply that each of these three parameters has been properly initialized with a value. The postcondi- tion is that all occurrences of the first character have been replaced by the second character.

As in our previous string-processing methods, the limiting case in this Head-and-tail algorithm

problem is the empty string, and the recursive case will divide the string into its head and its tail. If the head is the character we want to replace, we concatenate its substitute with the result we obtain by recursively converting its tail.

This analysis leads to the definition shown in Figure 12.10. This method has more or less the same head and tail structure as the preceding exam- ple. The difference is that here the operation we perform on the head of the string is concatenation rather than addition.

The base case is still the case in which str is the empty string. The first recursive case occurs when the character being replaced is the head of str. In that case, its substitute (ch2) is concatenated with the result of converting the rest of the string and returned as the result. The second recursive case occurs when the head of the string is not the character be- ing replaced. In this case, the head of the string is simply concatenated with the result of converting the rest of the string. Figure 12.11 shows an example of its execution.

Figure12.11:Atraceof convert("bad",’d’,’m’), which returns “bam.”

Figure 12.10: The convert() method replaces one character with another in a string.

convert("bad",'d','m');

Result

'b' + 'a' + 'm' + "" = "bam"

'a' + 'm' + ""

'm' + ""

Base case

SELF-STUDY EXERCISE

EXERCISE 12.11 Write a recursive method that changes each blank in a string into two consecutive blanks, leaving the rest of the string unchanged.

Printing all Possible Outcomes when Tossing N Coins

Suppose that a student who is studying probability wishes to have a Java program that, for any positive integer N, will print out a list of all possible outcomes when N coins are tossed. For purposes of analyzing the prob- lem, it is assumed that the coins are numbered 1 through N and that they are tossed one at a time. An outcome will be represented by a string of

Hs and Ts corresponding to heads and tails. Thus, if N = 2, the string HT

represents a head on the first coin and a tail on the second coin. What we

need is a method which, when given the number of coins, will print outA coin tossing experiment

all strings of this type. In case of two coins the output should be:

Let’s devise a strategy, given any positive integer N, for printing the

strings that correspond to all possible outcomes when tossing N coins. Designing a recursive algorithm

Clearly, for N = 1, the method needs to print an H on one line and a T on the next line. For an arbitrary number of coins N, one way to generate all outcomes is to think of two kinds of strings—those that start with an H and those that start with a T. The strings that start with H can be generated by inserting an H in front of each of the outcomes that occur when N 1 coins are tossed. The strings beginning with T can be generated in a similar manner. Thus, using the outcomes for two coins above, we know that the outcomes for three coins for which the first coin is H are:

Using an argument similar to the one above, we can generalize this to a description of the recursive case for an algorithm. We want an algorithm that generates all those outcomes for N coins where we are given a string STR representing one particular outcome for all but the last K coins where 0 < K <= N. To print out all such outcomes, just print all outcomes with a fixed outcome corresponding to STR + "H" for all but the last K 1 coins and then print all outcomes with the fixed outcome STR + "T" for all but the last K 1 coins. The base case is the special case K = 1 when you just need STR + "H" on one line and STR + "T" on the next. If you start the algorithm with STR = "" and K = N, this algorithm will print out all the outcomes for tossing N coins.

To translate this into Java code we can create a class called Coin- Toss which has a single static method called printOutcomes(String str,int N). The above recursive description easily translates into code for the method in Figure 12.12.

To print out all outcomes when tossing, say, seven coins, just make the method call CoinToss.printOutcomes("",7). This particular call would generate the desired output:

Figure 12.12: The method printOutcomes() prints all outcomes given the results on some initial coins.

To better understand how the recursive method definition generates its output, it might be helpful to trace the order of recursive calls and output to System.out that occurs when executing printOutcomes("",3) as shown in Figure 12.13.

Notice that the recursive case in the method implementation makes two calls to itself and as a result it is not so clear how this method would be written using a loop instead of recursion. This example is more typical of the type of problem for which a recursive method is shorter and clearer than a method that solves the same problem without using recursion.

Figure 12.13: The order in which the recursive calls and output occur when printOutcomes("",3) is executed.

SELF-STUDY EXERCISE

EXERCISE 12.12 Modify the above printOutcomes() method so that it will print out all possible outcomes when a chess player plays a series of N games. The outcome of each game is to be represented by a W, L, or D corresponding to the player winning, losing, or drawing the game.