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
Your number must be: 666
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.
