In chapter 3 we saw that the if-else construct enables us to equip our programs with the ability to make decisions. In chapter 4 we are going to see a variety of constructs that allow us to build repetition into our programs.
The basic repetition construct in Java is the while loop. Its basic structure is as follows.
while(<test>) {
<statements to be repeated>
}
When program execution first reaches the while statement, the test gets evaluated. If the test evaluates to true, execution enters the body of the loop and the statements inside the pair of curly braces gets executed. After execution of the body statements, we return again to the test. If the test evaluates to true again, we make another pass through the body. This process repeats until eventually the test evaluates to false. At that point, execution continues with the next statement after the body.
When writing a while loop you have to take care to ensure that the statements in the body will allow you to eventually reach a state where the loop test evaluates to false. If not, your program will stay stuck in the loop forever. (This condition is known as an infinite loop.)
One of the more common applications of loops uses an integer variable called a loop counter to control the behavior of the loop. Here is a typical example - the goal of the code below is to print a table of values for 2n as n ranges from 0 to 14.
public static void main(String[] args) {
int n,power;
n = 0;
while(n < 15) {
power = (int) Math.pow(2, n);
System.out.println("2 to the power " + n + " is " + power);
n = n + 1;
}
}
The variable n in the example acts as the loop counter. Before we enter the loop we give n an initial value of 0. The loop test monitors the current value of n and stops the repetition when n reaches the value 15. Finally, the last statement in the loop ensures that the value of n goes up by 1 on each trip through the loop. This guarantees that the loop will eventually terminate.
That statement
n = n + 1;
is commonly referred to as an increment statement. It causes the value stored in n to increase by 1 each time we evaluate the statement. This is such a common type of statement that Java offers a convenient short-cut form:
n++;
that does the same thing.
The code above uses the exponentiation function Math.pow() to compute 2n on each iteration of the loop. This is certainly correct, but can be done more efficiently by making use of a common optimization. The code below shows an optimized alternative.
public static void main(String[] args) {
int n,power;
n = 0;
power = 1;
while(n < 15) {
System.out.println("2 to the power " + n + " is " + power);
// These next two statements maintain the invariant that power = 2^n
n++;
power = power*2;
}
The optimization here is based on the observation that if you have already computed, say, 210, and have stored that value in a variable named power, you can compute 211 more easily by just computing power*2 (which equals 210*2 = 211) and making that be the new value for power.
A somewhat more sophisticated way to explain this optimization is to say that the code here is designed to maintain an invariant, which is a logical relationship between the various variables involved. In this case, the invariant we are maintaining is the mathematical relationship
Note that that initialization statements
n = 0; power = 1;
that we execute before the start of the loop are chosen to make the invariant true before we enter the loop:
The last two statements in the loop body are designed to maintain the truth of the invariant as we increase n. If power = 2n and we increase n by 1, we have to multiply power by 2 to guarantee that the relationship between power and 2n is maintained.
A common application that while loops are useful for is adding up lists of numbers. If the numbers to be added follow a simple and predictable pattern, it is relatively easy to write the logic needed to add the numbers up.
Here is a simple example. Suppose we wanted to compute the sum
for some integer N. The following code does that calculation.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter a value for N: ");
int N = input.nextInt();
double sum = 0.0;
int n = 1;
double term;
while (n <= N) {
term = 1.0/n;
sum = sum + term;
n++;
}
System.out.println("The sum is " + sum);
}
In addition to the usual loop counter variable, n, which counts the number of terms we have added to the sum, we also use a second variable, sum, that stores the running total. On each iteration of the loop we compute the next term to be added to the sum, add it to the running total, and then increment the counter. If the relationship between the loop counter and the term we are trying to generate is simple, this strategy is very easy to implement.
In the next example, the relationship between the loop counter and the term we are adding to the running total gets a little more complicated. In this example, we want to compute the sum
where
is the factorial of N. Those of you who have had Math 150 may know that in the limit as N gets very large this sum converges to e = 2.71828182846...
It is easy to see that if the loop counter for this sum runs from n = 1 up to n = N, the term we need to add to the running total when the counter is n is 1/n!. The problem is that we have no easy way to compute n!.
The solution to this difficulty is to use the loop invariant idea again. This time, the loop invariant we want to maintain looks something like
If we increase n by 1, we have to replace term by (term/n) to keep the invariant true.
The following code implements these ideas to correctly compute the sum.
public static void main(String[] args) {
int n, N;
double term, sum;
System.out.print("Enter the number of terms: ");
Scanner input = new Scanner(System.in);
N = input.nextInt();
n = 1;
sum = 1.0;
term = 1.0;
while (n <= N) {
sum = sum + term;
// Maintain the invariant that term = 1/n!
n++;
term = term / n;
}
System.out.println("Sum = " + sum);
System.out.println("e = " + Math.E);
}
Here is a final, more complex example that demonstates the power of these ideas. In Math 150 you learn that various functions can be computed by a method called power series. One important application of this idea is the power series to compute the function sin(x).
If we label the terms of this sum with a loop counter n that ranges from n = 0 upward in steps of 1, the relationship between the term and the loop counter n is given by the invariant
The invariant tells us that if we increase the counter by 1, we have to multiply term by a factor of
to maintain the invariant relationship.
The following code uses that invariant relationship to correctly compute the sum we want to compute.
public static void main(String[] args) {
int n, N;
double x, term, sum;
Scanner input = new Scanner(System.in);
System.out.print("Enter the number of terms: ");
N = input.nextInt();
System.out.print("Enter the value of x: ");
x = input.nextDouble();
n = 0;
sum = 0.0;
term = x;
while (n < N) {
sum = sum + term;
// Maintain the invariant that term = (-1)^n x^(2n+1)/(2n+1)!
n++;
term = -term * x * x / ((2 * n) * (2 * n + 1));
}
System.out.println("Sum = " + sum);
System.out.println("Sin(x) = " + Math.sin(x));
}
The while loop described above is the basic repetition construct in Java. In addition to while, Java offers a couple of alternative forms that may be more appropriate in certain circumstances.
The first of these alternative forms is the do-while statement.
do {
<statements to be repeated>
} while(<test>);
In the do-while statement the relative location of the body and test changes. In a while, the <test> is evaluated for the first time before we get a chance to run the body statements. In a do-while loop, the body gets evaluated before the <test>. In some cases, the <test> will not even make sense until we have had a chance to execute the code in the body at least once. In those situations, the do-while is the appropriate form to use.
Here is a typical example of a do-while application. Sometimes when we prompt the user for input we want to ensure that the input they provide meets specific criteria. A do-while construct is useful for enforcing input criteria, because it allows us to test the input that the user has provided and return to the prompt if the input appears to be invalid:
int n;
do {
System.out.print("Enter a positive integer: ");
n = input.nextInt();
} while(n < 0);
Note that for this to work correctly we have to run the body before the test, because the body provides a value for n. Until n has a value, it makes no sense to try to evaluate the test, n < 0.
A second alternative is the for loop. Many applications of the while loop (especially applications that use a loop counter) take the following form:
<initialize counter>
while(<counter less than end value>) {
<statements using counter>
<increment counter>
}
or, more compactly
<initialization>
while(<test>) {
<body>
<increment>
}
The for loop takes these elements and organizes them like so:
for(<initialization>;<test>;<increment>) {
<body>
}
Functionally, these two forms do exactly the same things. In some cases you will find the for loop more convenient to write.
Here is a typical example. The code below computes the sum of the squares of the first N integers.
int sum = 0;
int n;
for(n = 1;n <= N;n++) {
sum = sum + n*n;
}
This form is equivalent to
int sum = 0;
int n = 1;
while(n <= N) {
sum = sum + n*n;
n++;
}