Write a program that asks the user to think of an integer between 1 and 1,000,000, and then guesses the number through a series of yes/no questions. To guess the number, the program calls a recursive function guess that has two parameters, low and high. The precondition for the function requires that the user’s number lie in the range low...high so that the program’s initial call is to guess(1, 1000000). What is a good stopping case for guess, when it can guess the user’s number with little or no work? If (low == high), then there is only one possible number, and the function can guess that number. On the other hand, if (low < high), then the function should calculate a point near the middle of the range:

Here is the JAVA program:

import java.util.Scanner;   //to accept input from user

public class Main  {  //class name

public static void main(String[] args)  { //start of main functions

   System.out.println("Think of a number between 1 and 1000000");  //prompts user to think of number between the given range

    guess(1 , 1000000);  }  //calls guess method by passing values of low and high to it

public static void guess(int low, int high)  { //method that takes two parameters high and low and guesses the number through yes/no questions

Scanner scan = new Scanner(System.in);  //creates Scanner class object to take input from user

String input;  //to store choice of user

int middle;  //computes the midpoint of the high and low values

if(low == high)  {  //if there is only one possible number

 System.out.println("The guessed number is: " + low); //displays that one number

 System.exit(0);  }  //the program exits

if(low < high)  {  // if value of low is less than that of high

  middle = (low + high) / 2;  //computes the mid point of high and low values

  System.out.println("Is "+middle+" your number?");  //prompts user if middle value is that number

  input = scan.next();  //reads choice from user

  if(input.equals("yes"))  {  //if user enters yes then this means the guessed number is right

   System.out.println("The guessed number is: " + middle);  //displays the guessed number

   System.exit(0);    }

   if(input.equals("n"))  {  //if user enters no then this means the guessed number is not right and more questions are asked

System.out.println("Is the number greater or less than " + middle + " ?");  //asks user if number is greater than or less to the computed midpoints

System.out.println("Enter g for greater and l for less: ");   //asks user to type g for greater and l for less

  input = scan.next();  //reads the choice from user

  if(input.equals("g")) { //if user choice is equal to g

  guess(middle+1, high);  }  //calls guess function recursively by using the values greater than the middle point to high

   if(input.equals("l"))  {  //if user choice is equal to l

     guess(low, middle -1);  }  }  }  }       } //calls guess function recursively by using the value in low to that of the middle point

Explanation:

Lets say the values are:

low = 1

high = 1000000

So the guess function works as follows:

if(low == high) this condition evaluates to false because value of low is not equal to that of high.

if(low < high) this condition evaluates to true so the program control moves inside the body of this if statement:

middle = (low + high) / 2;  This computes the mid point so it becomes:

middle = (1+ 1000000) / 2;  

middle = 500000.5

Asks user if the guess is correct. If user enters yes then display the guessed number of output else ask the user if the number is greater than or less than the value.

If user enters "g" which means the value if greater than midpoint value, then the statement:  guess(middle+1, high); is computed otherwise statement a

guess(low, middle -1); is computed.

Suppose user enter "g". So this statement calls guess function recursively by passing the value of middle+1 i.e. 500001.5 and value of high = 1000000 . Now repeat the same steps like the start of guess function. Same code is used if the user enters "l" then statement guess(low, middle -1);  becomes

guestt (1, 499999.5)  Now repeat the same steps like the start of guess function.

The program along with the output is attached.