13.4 Recursion or Iteration? | 651through data[last]). If we want to print the array elements in reverse order recursively, we
simply swap the two statements within the ifstatement.
Binary Search
Do you remember the binary search in Chapter 11? Here is the description of the algorithm:
“The algorithm divides the list in half (divides by 2—that’s why it’s called a binarysearch) and
decides which half to look in next. Division of the selected portion of the list is repeated un-
til the item is found or it is determined that the item is not in the list.” There is something
inherently recursive about this description.
Although the method that we wrote in Chapter 11 was iterative, it really is a recursive al-
gorithm. The solution is expressed in terms of smaller versions of the original problem: If the
answer isn’t found in the middle position, perform a binary search (a recursive call) to search
the appropriate half of the list (a smaller problem). In the iterative version, we kept track of
the bounds of the current search area with two local variables,firstand last. In the recur-
sive version, we call the method with these two values as arguments. We must call the re-
cursive binary search method from the isTheremethod of the SortedListclass rather than
writing it as part of that method.
private booleanbinIsThere(int first, int last, int item)
// Returns true if item is in the list
{
if (first > last) // Base case 1
return false;
else
{
int midPoint;
midPoint = (first + last) / 2;
if (item < listItems[midPoint])
returnbinIsThere(first, midPoint-1, item);
else if(item == listItems[midPoint])
return true; // Base case 2
else
returnbinIsThere(midPoint+1, last, item);
}
}
public booleanisThere(int item)
// Returns true if item is in the list
{
returnbinIsThere(0, numItems-1, item);
}
13.4 Recursion or Iteration?
Recursion and iteration are alternative ways of expressing repetition in an algorithm. When
iterative control structures are used, processes are made to repeat by embedding code in a