Java Reference
In-Depth Information
Is your number higher(h), lower(l), or equal(e) to: 750: l
Is your number higher(h), lower(l), or equal(e) to: 625: h
Is your number higher(h), lower(l), or equal(e) to: 687: l
Is your number higher(h), lower(l), or equal(e) to: 656: h
Is your number higher(h), lower(l), or equal(e) to: 671: l
Is your number higher(h), lower(l), or equal(e) to: 663:
h
Is your number higher(h), lower(l), or equal(e) to: 667:
l
Is your number higher(h), lower(l), or equal(e) to: 665:
h
Let us examine the guess method. The interval and the guess are passed as parameters.
Every time there is a recursive call, the interval is reduced by half and the guess is placed
in the middle of the interval. The code System.exit(0) guarantees that the code will exit
after the solution is found. Therefore, we keep calling the guess method and the guess
method never returns to the calling method. Note that in this program we cannot replace
System.exit(0) with return . The reason is that we do not want to return to the calling
method. This program is a case where a recursive solution is not needed because all the
recursive calls are at the end of execution paths. Applying our knowledge of tail recursion,
we can rewrite the code as follows.
public static void guess( int low , int high , int guess)
{
while ( true ) {
if (low == high) {
System. out . println ( "Your number must be: " +low);
System. exit(0) ;
System. out . print ( "Is your number higher(h), lower(l), or equal(e)
to: " +guess+ ": " );
Scanner keyboard = new Scanner(System. in) ;
String result = keyboard.next() ;
switch ( result . charAt (0) )
{
case 'h' :
low=guess + 1;
guess = (guess + high + 1) / 2;
break ;
case 'l' :
high = guess
1;
guess = (low + guess
1) / 2;
break ;
case
:
System. out . println ( "I win again!" );
System. exit(0) ;
'e'
}
}
}
Note that the original recursive call had several execution paths. Since each path led to
a single recursive call and this call was the last call for that branch, we were able to rewrite
the code using the tail recursion principle.
We solved the problem using the ' divide-and-concur approach. We kept reducing the
size of the original array until there was a single number in it. Let us next see if we can
apply the same approach to a slightly different application. Suppose that we are given a
sorted array of distinct numbers and we want to find the index of a specific number in the
array. For example, consider the following sorted array of integers.

Search WWH ::

Custom Search