Java, Java, Java

 

 

Like strings, arrays also have a recursive structure. Just as each substring of a string is similar to the string as a whole, each portion of an array is similar to the array as a whole. Similarly, just as a string can be divided into a head and a tail, an array can be divided into its head, the first ele- ment, and its tail, the rest of its elements (Fig. 12.14). Because the tail of an

 

 

HeadTail

 

array is itself an array, it satisfies the self-similarity principle. Therefore,

arrays have all the appropriate characteristics that make them excellent

 

candidates for recursive processing.

 

Recursive Sequential Search

Let’s start by developing a recursive version of the sequential search al- gorithm that we discussed in Chapter 9. Recall that the sequential search

Figure 12.14: An array of int is a recursive structure whose tail is similar to the array as a whole.

 

method takes two parameters: the array being searched and the key, orMethod design

target value, being searched for. If the key is found in the array, the method returns its index. If the key is not found, the method returns 1, thereby indicating that the key was not contained in the array. The

iterative version of this method has the following general form:

,,

 

 

 

 

 

 

 

 

J

If we divide the array into its head and tail, then one way to describe a recursive search algorithm is as follows:

,,

 

 

 

J

This algorithm clearly resembles the approach we used in recursive string processing: Perform some operation on the head of the array and recurse on the tail of the array.

The challenge in developing this algorithm is not so much knowing

what to do but knowing how to represent concepts like the head and the How do we represent head and tail?

tail of the array. For strings, we had methods such as s.charAt(0) to represent the head of the string and s.substring(1) to represent the string’s tail. For an array named arr, the expression arr[0] represents the head of the array. Unfortunately, we have no method comparable to

 

 

 

 

 

 

 

 

 

 

 

Figure 12.15: A parameter, head, can represent the head of some portion of the array.

the substring() method for strings that lets us represent the tail of the array.

To help us out of this dilemma, we can use an integer parameter to rep- resent the head of the array. Let’s have the int parameter, head, represent the current head of the array (Fig. 12.15). Then head + 1 represents the start of the tail, and arr.length-1 represents the end of the tail. Our method will always be passed a reference to the whole array, but it will restrict the search to the portion of the array starting at head. If we let head vary from 0 to arr.length on each recursive call, the method will recurse through the array in head/tail fashion, searching for the key. The method will stop when head = arr.length.

 

0N-1

First call

 

HeadTail

 

Second call

 

HeadTail

 

Third call

 

 

 

HeadTail

0N-1

 

 

Last call

 

 

Head

 

 

 

 

 

 

 

 

 

 

 

 

Recursion parameter

This leads to the definition for recursive search shown in Figure 12.16. Note that the recursive search method takes three parameters: the array to be searched, arr, the key being sought, and an integer head that gives the starting location for the search. The algorithm is bounded when head

= arr.length. In effect, this is like saying the recursion should stop when we have reached a tail that contains 0 elements. This underscores the point we made earlier about the importance of parameters in design-

ing recursive methods. Here the head parameter serves as the recursion parameter. It controls the progress of the recursion.

Note also that for the search algorithm we need two base cases. One represents the successful case, where the key is found in the array. The other represents the unsuccessful case, which comes about after we have looked at every possible head in the array and not found the key. This

 

,,

 

 

 

 

 

 

 

 

 

 

J

Figure 12.16: The recursive search method takes three parameters. The head parameter points to the beginning of that portion of the array that is being searched.

 

 

case will arise through exhaustion—that is, when we have exhausted all possible locations for the key.

 

 

 

 

Information Hiding

Note that in order to use the search() method, you would have to know that you must supply a value of 0 as the argument for the head parameter. This is not only awkward but also impractical. After all, if we want to search an array, we just want to pass two arguments, the array and the

key we’re searching for. It’s unreasonable to expect users of a method to Design issue

know that they also have to pass 0 as the head in order to get the recursion started. This design is also prone to error, because it’s quite easy for a mistake to be made when the method is called.

For this reason, it is customary to provide a nonrecursive interface to the recursive method. The interface hides the fact that a recursive algo- rithm is being used, but this is exactly the kind of implementation detail that should be hidden from the user. This is an example of the principle

of information hiding that we introduced in Chapter 0. A more appropri- Hide implementation details

ate design would make the recursive method a private method that’s called by the public method, as shown Figure 12.17 and implemented in the Searcher class (Fig. 12.18).

 

Figure 12.17:The public search() method serves as an interface to the private recur- sive method, search(). Note that the methods have different signatures.

 

,,

public c l a s s Searcher {

/ ∗ ∗

∗ s e a r c h ( a r r , k e y ) −− s e a r c h e s a r r f o r k e y .

∗ P r e :a r r ! = n u l l a n d 0 <= h e a d <= a r r . l e n g t h

∗ P o s t : i f a r r [ k ] == k e y f o r k ,0 <= k < a r r . l e n g t h ,

∗r e t u r n k ,e l s e r e t u r n −1

∗/

public in t search ( in t ar r [ ] , in t key )

return search ( arr , 0 , key ) ; // C a l l r e c u r s i v e s e a r c h

}

/ ∗ ∗

∗ s e a r c h ( a r r , h e a d , k e y ) −− R e c u r s i v e l y s e a r c h a r r f o r k e y

∗s t a r t i n g a t h e a d

∗ P r e :a r r ! = n u l l a n d 0 <= h e a d <= a r r . l e n g t h

∗ P o s t : i f a r r [ k ] == k e y f o r k ,0 <= k < a r r . l e n g t h , r e t u r n k

∗e l s e r e t u r n −1

∗/

private in t search ( in t ar r [ ] , in t head , in t key ){

i f ( head == a r r . length )// B a s e c a s e : e m p t y l i s t − f a i l u r e

return −1;

e ls e i f ( a r r [ head ] == key ) // B a s e c a s e : k e y f o u n d −− s u c c e s s

return head ;

e ls e// R e c u r s i v e c a s e : s e a r c h t h e t a i l

return search ( arr , head + 1 , key ) ;

// s e a r c h ( )

public s t a t i c void main ( S t r i n g args [ ] )

in t numbers [ ] =0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 1 8 ;

Searcher searcher = new Searcher ( ) ;

for ( in t k = 0 ; k <= 2 0 ; k++)

in t r e s u l t = searcher . search ( numbers , k ) ;

i f ( r e s u l t ! =1)

System . out . p r i n t l n ( k + ” found at ” + r e s u l t ) ;

e ls e

System . out . p r i n t l n ( k + ” i s not in the array ” ) ;

} // f o r

} // m a i n ( )

// S e a r c h e r

\J

Figure 12.18: Information hiding principle: The public search() method calls the private, recursive search(), thereby hiding the fact that a recursive algorithm is used.

 

SELF-STUDY EXERCISE

EXERCISE 12.13 Write a main() method for the Searcher class to conduct the following test of search(). Create an int array of ten el- ements, initialize its elements to the even numbers from 0 to 18, and then use a for loop to search the array for each of the numbers from 0 to 20.

Recursive Selection Sort

Next we want you to think back to Chapter 9, where we introduced the selection sort algorithm. To review the concept, suppose you have a deck of 52 cards. Lay them out on a table, face up, one card next to the other.

Starting at the last card, look through the deck, from last to first, find the Sorting a deck of cards

largest card and exchange it with the last card. Then go through the deck again starting at the next to the last card, find the next largest card, and exchange it with the next to the last card. Go to the next card, and so on. If you repeat this process 51 times, the deck will be completely sorted.

 

 

Let’s design a recursive version of this algorithm. The algorithm we just described is like a head-and-tail algorithm in reverse, where the last card in the deck is like the head, and the cards before it are like the tail. After each pass or recursion, the last card will be in its proper location, and the cards before it will represent the unsorted portion of the deck. If we use parameter to represent last, then it will be moved one card to the left at each level of the recursion.

Figure 12.19 illustrates this process for an array of integers. The base case is reached when the last parameter is pointing to the first element in the array. An array with one element in it is already sorted. It needs no re- arranging. The recursive case involves searching an ever-smaller portion of the array. This is represented in our design by moving last down one element to the left.

 

After one pass

 

 

 

 

 

 

 

 

 

 

 

Figure 12.19: Selection sort: Us- ing a head-and-tail algorithm in reverse to sort an integer array.

 

Unsorted

 

 

 

 

Unsorted

 

 

 

 

Unsorted

Last

 

Last

 

Last

 

After two passes

 

 

 

After three passes

 

 

 

After last pass

 

Last

 

,,

 

 

 

 

 

 

 

 

 

 

J

Figure 12.20: The selection- Sort() method uses the findMax() and

swap() methods to help it sort an array.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Task decomposition

Figure 12.20 provides a partial implementation of selection sort for an array of int. In this definition, the array is one parameter. The second parameter, int last, defines that portion of the array, from right to left, that is yet to be sorted. On the first call to this method, last will be arr.length 1. On the second, it will be arr.length 2, and so on. When last gets to be 0, the array will be sorted. Thus, in terms of the card deck analogy, last represents the last card in the unsorted portion of the deck.

Note how simply the selectionSort() method can be coded. Of course, this is because we have used separate methods to handle the tasks of finding the largest element and swapping the last element and the largest. This not only makes sense in terms of the divide-and-conquer principle, but we also already defined a swap() method in Chapter 9. So here is a good example of reusing code:

,,

 

 

 

 

 

 

 

 

 

J

 

The definition of the findMax() method is left as a self-study exercise.

 

SELF-STUDY EXERCISES

EXERCISE 12.14 As in the case of the search() method, we need to provide a public interface to the recursive selectionSort() method. We want to enable the user to sort an array just by calling sort(arr), where arr is the name of the array to be sorted. Define the sort() method.

EXERCISE 12.15 Define an iterative version of the findMax(arr,N) method that is used in selectionSort(). Its goal is to return the location (index) of the largest integer between arr[0] and arr[N].