Recursion - Absolute Java - page 668

To see that this is the correct value to return, note that, if power(x, n - 1) returns
the correct value, then power(x, n - 1) returns x n-1 and so power(x, n) returns

x n-1 * x , which is x n

This is the correct value for power(x, n) .

That is all you need to check to be sure that the definition of power is correct. (The
previous technique is known as mathematical induction , a concept that you may have
heard about in a mathematics class. However, you do not need to be familiar with the
term mathematical induction to use this technique.)
We gave you three criteria to use in checking the correctness of a recursive method
that returns a value. Basically, the same rules can be applied to a recursive void
method. If you show that your recursive void method definition satisfies the following
three criteria, then you will know that your void method performs correctly:
1. There is no infi nite recursion.
2. Each stopping case performs the correct action for that case.
3. For each of the cases that involve recursion, if all recursive calls perform their
actions correctly, then the entire case performs correctly.

criteria for
void methods

Binary Search ★
In this subsection, we will develop a recursive method that searches an array to find out
whether it contains a specified value. For example, the array may contain a list of the
numbers for credit cards that are no longer valid. A store clerk needs to search the list
to see if a customer's card is valid or invalid.
The indices of the array a are the integers 0 through finalIndex . To make the task
of searching the array easier, we will assume that the array is sorted. Hence, we know
the following:

a[0] ≤ a[1] ≤ a[2] ≤ … ≤ a[finalIndex]

In fact, the binary search algorithm we will use requires that the array be sorted
like this.
When searching an array, you are likely to want to know both whether the value is
in the array and, if it is, where it is in the array. For example, if you are searching for a
credit card number, then the array index may serve as a record number. Another array
indexed by these same indices may hold a phone number or other information to use
for reporting the suspicious card. Hence, if the sought-after value is in the array, we
will have our method return an index of where the sought-after value is located. If the
value is not in the array, our method will return -1 . (The array may contain repeats,
which is why we say “an index” and not “the index.”)
Now let us proceed to produce an algorithm to solve this task. It will help to
visualize the problem in very concrete terms. Suppose the list of numbers is so long
that it takes a book to list them all. This is in fact how invalid credit card numbers are
distributed to stores that do not have access to computers. If you are a clerk and are