C SC 160 Chapter 6: Repetition Statements
major resource: An Introduction to Object-Oriented Programming with Java, fourth edition, Wu, McGraw Hill, 2006

[ previous | schedule | next ]

secondary resource: Programming and Problem Solving with Java, Slack, Brooks/Cole, 2000

where:

• condition is a boolean expression.  If true, the loop body is executed.  If false, execution flow transfers to the statement following the loop.
• body is collection of zero or more Java statements.  If the body is empty, the for and while constructs allow you to replace the brackets with a single semi-colon.
• initialization is a Java statement, normally definition and initialization of an int variable which serves as loop counter.  It is optional.
• increment is a Java statement, normally pre- or post-increment of the loop counter variable.  It is optional.

Execution sequence of a while loop:

while ( condition ) {
   body
}

1. The condition is evaluated.
2. If condition is true, then execution flow proceeds to step 3, else it proceeds to statement following the loop.
3. The loop body is executed.
4. Execution flow returns to step 1.

Execution sequence of a do-while loop:

do {
   body
} while ( condition );

1. The loop body is executed.
2. The condition is evaluated.
3. If condition is true, then execution flow returns to step 1, else it proceeds to statement following the loop.

Execution sequence of a for loop:

for  ( initialization ; condition ; increment ) {
   body
}

1. The initialization statement is executed.
2. The condition is evaluated.
3. If condition is true, then execution flow proceeds to step 4, else it proceeds to statement following the loop.
4. The loop body is executed.
5. The increment statement is executed.
6. Execution flow returns to step 2.

Although you have just seen that either for or while loops can easily mimic the other, there are conventional uses for each of the looping constructs.

Counting loops and for

When the number of iterations of a loop can be calculated before execution of the loop begins, it is often referred to as a counting loop.  By convention, counting loops are implemented using for loops, using an auxiliary counter variable defined in the initialization and maintained in the increment.

Sentinel-controlled loops and while, do-while

When the number of loop iterations cannot be calculated in advance but instead depends on a condition which changes as a result of a statement execution in the loop body, it is often referred to as a sentinel-controlled loop, or event-controlled loop.  The sentinel is a specific value. The event is the statement which causes the condition to flip from true to false.  By convention, sentinel-controlled loops are implemented using while loops and, less frequently, do-while loops.

Distinguishing while and do-while

Simply put, while tests the termination condition before entering the loop body (pre-test loop) and do-while tests it after executing the loop body (post-test loop).  Therefore, a do-while loop is guaranteed to iterate at least once.  It is possible to check the termination condition within the loop body (loop-and-a-half control) using the break statement, explained below.

do-while is frequently used for loops containing an input statement, where a specific input value (the sentinel) signals the end of input.  The loop body must execute at least once to get any input at all.  The loop is structured so that when the sentinel value is read, the loop condition goes from true to false and the loop is exited.  There is an example below, in the discussion of break.

Inverting a Boolean expression

• Frequently need to invert design logic to correctly form loop termination expression.
• Why? Because we think of looping "until" rather than looping "while"
• Example: design requirement stated in English as "continue looping until the sum is greater than 21".
• Java does not have “until”, so expression must be inverted.
• Could be translated into Java as: while (!(sum > 21))
• Usually translated as   while (sum <= 21)
• Both are equivalent, because opposite of > is <=
• Example "continue looping until either the sum is greater than 21 or the number of values included in the sum is at least 5"
• Could be translated into Java as: while (!((sum > 21) || (count >= 5)))
• Usually translated as   while ((sum <= 21) && (count < 5))
• Second version is derived from first by applying DeMorgan’s laws for distributing NOT over an expression
• !(A || B) is the same as !A && !B
• !(A && B) is the same as !A || !B
• if A and B are expressions using relational operators, !A and !B can be written using opposite relational operator, eliminating explicit “!”
• in general, try to minimize explicit use of NOT.  Second version in these examples is preferred

The "off by one" error

Example: calculate the sum of the values 1 through 100

int sum = 0;
for (int i=1; i<100; i++) {
   sum = sum + i;
}
System.out.println(sum);

Example: calculate the sum of the values stored in array arr

int[] arr = { 6, 15, -87, 928, 72, 909 };
int sum = 0;
for (int i=0; i<=arr.length; i++) {
   sum = sum + arr[i];
}
System.out.println(sum);

Reasoning about loops: loop termination

Is there any way to prove that a loop will terminate? In some cases, you can see that it does from casual observation, but we will formalize it just a little.

One quick check: Check each variable in the loop termination condition to see if its value is modified in the loop body (or increment part of for loop). At least one such variable must be changed! If not, then the loop condition can never switch from true to false.

Example: calculate the sum of the integers 1 through 7, using for loop. Will it terminate? Can you show it will terminate?

int result = 0;
for ( int counter=1; counter<=7; counter++ ) {
    result = result + counter;
}

We know this loop will terminate because:
1. counter, an integer, is initialized to 1
2. the loop is guaranteed to terminate when counter has a value of 8 or higher
3. at the end of each iteration, the value of counter is increased by 1.
4. 8 is greater than 1.

Example: Count the number of times a positive integer can be divided in half (using integer division) before its value becomes less than 1.  This estimates the logarithm base 2 of that number. Will it terminate? Can you show it will terminate?

int theNum = 256;
int log = -1;
while (theNum >= 1) {
   theNum = theNum / 2;
   log++;
}

Example: Calculate the largest number whose factorial is less than 1 million. Will it terminate? Can you show it will terminate?

int fact = 1;
int count = 0;
while (fact < 1000000) {
   count++;
   fact = fact * count;
}
System.out.println( (--count) ); // why decrement? why pre-decrement?

Would you believe the result of this is 9?  9 factorial is 362880. What is the purpose of the decrement?

Variation on this example: Initialize fact to 0 instead of 1. Will it terminate? Can you show it will terminate?

Example: Count from 1 to a user-entered value, by 3. (e.g. if input is 10, output is 1,4,7,10). Will it terminate? Can you show it will terminate?

int out = 1;
int limit = Integer.parseInt(JOptionPane.showInputDialog(null,"enter limit"));
while (out != limit) {
   System.out.print(out+",");
   out = out + 3;
}
System.out.println(limit);

Example: Calculate the sum of 10 user integer inputs. Will it terminate? Can you show it will terminate?

int sum = 0;
int count = 0;
int input;
while (count < 10) {
   input = Integer.parseInt(JOptionPane.showInputDialog(null,"enter value"));
   sum = sum + input;
}

Example: Count the number of thirds in a unit. Will it terminate? Can you show it will terminate?

int count = 0;
double sum = 0.0;
while (sum != 1.0) {
   count++;
   sum = sum + 0.3333333;
}
System.out.println(sum);

In general, proving a loop will terminate is a difficult task.  If you can achieve it, however, you have made a very strong statement about your program.

Loop termination condition is tested only at beginning (while, for) or end (do-while) of loop, regardless of when the condition flips from true to false.

Suppose we want to exit the loop in the middle? Use an if statement that includes a break statement. Execution of a break statement causes execution flow to be immediately transferred to the statement following the loop.

This frequently happens when doing sentinel-controlled looping based on user/file input. You want to escape from the loop as soon as the sentinel value is input to avoid processing it.

Example:  sentinel value.  method computes sum of integers entered at keyboard until -1 (the sentinel) is entered, at which time it outputs the sum.

It is tempting to write the solution as:

This does not work correctly.  What is the problem with the above code?

Here is an alternative solution:

int sum = 0;
int input = 0;
String strValue;
while (input >= 0) {
   strValue = JOptionPane.showInputDialog(null,"Enter value (-1 when finished)");
   input = Integer.parseInt(strValue);
   if (input >= 0) {
      sum = sum + input;
   }
}
JOptionPane.showMessageDialog(null,"The sum is "+sum);

This works fine, but note that the termination condition had to be specifed in two different places.  This goes against the "single point control" principle because if the termination condition needs to be modified at some future time the change must be made in two places in this loop.

Here is a solution using break

int sum = 0;
int input = 0;
String strValue;
while (true) {
   strValue = JOptionPane.showInputDialog(null,"Enter value (-1 when finished)");
   input = Integer.parseInt(strValue);
   if (input < 0) {
      break;
   }
   sum = sum + input;
}
JOptionPane.showMessageDialog(null,"The sum is "+sum);

Here is another way this code could have been written without break:

int sum = 0;

String strValue = JOptionPane.showInputDialog(null,"Enter value (-1 when finished)");
int input = Integer.parseInt(strValue);
while (input >= 0) {
   sum = sum + input;
   strValue = JOptionPane.showInputDialog(null,"Enter value (-1 when finished)");
   input = Integer.parseInt(strValue);
}
JOptionPane.showMessageDialog(null,"The sum is "+sum);

The logic is a more difficult to follow and the input statement has to be written twice. This is a common solution approach, however.

Here is yet another alternative, which uses do-while (note that input is used before getting its first value from user):

int sum = 0;
int input = 0;
String strValue;
do {
   sum = sum + input;
   strValue = JOptionPane.showInputDialog(null,"Enter value (-1 when finished)");
   input = Integer.parseInt(strValue);
} while (input >= 0);
JOptionPane.showMessageDialog(null,"The sum is "+sum);

Nested Loops

Example:

int total = 0;
for (int i=1; i<10; i++) {
   int sub = 0;
   while (sub < 1000) {
      sub = sub + i * 5;
   }
   total = total + sub;
}

• Nested loops have the potential for really chewing up CPU cycles. There are some performance-enhancing tips below.
• If an inner loop contains a break statement, it breaks out only from the innermost loop that contains it.

Improving loop performance

Since most of a program's runtime is spend in loops, even small changes can have a dramatic effects.  This is offset somewhat by use of optimizing compilers, which will recognize some of the situations below and automatically rearrange code to improve runtime performance.

Tip: Any part of an expression that can be calculated before the loop, should be.  It can be, if it involves variables not defined or modified elsewhere in the loop.  By moving it above the loop, it is calculated only once instead of on every iteration.

Example:

for (int i = 0;  i < max * modifier + 5; i++) {
   sum = sum + i;
}

should be changed to some thing like:

int limit = max * modifier + 5;
for (int i = 0; i < limit; i++) {
   sum = sum + i;>
}

Note:  it is considered poor form to use a for loop when a variable in the termination check is modified in the loop body.  In such cases, use a while loop instead.

while (i < limit) {
   chill = iomega * i + 6;
   result = (1.8 * cent + 32.0) / chill;
   i = i + 2;
}

can be changed to something like:

double fahr = 1.8 * cent + 32.0;
while (i < limit) {
   chill = iomega * i + 6;
   result = fahr / chill;
   i = i + 2;
}

Additional Loop Examples

int result = 1;
for ( int counter=1; counter<=4; counter++ ) {
    result = result * counter;
}

Why is result initialized to 1 instead of 0?

int result = 0;
for ( int counter=1; counter<=n; counter++ ) {
    result = result + counter;
}

What happens if n is 0?

What happens if you use "counter<n" rather than "counter<=n"?
for ( int counter=1; counter<n; counter++ )

What happens if you use "counter==n" rather than "counter<=n"?
for ( int counter=1; counter==n; counter++ )

Example: Loops can also run backward.  The last example can also be written

int result = 0;
for ( int counter=n; counter>=1; counter-- ) {
    result = result + counter;
}

You must be very careful when doing this!!

What happens if you use "counter<=1" rather than "counter>=1"?
for ( int counter=n; counter<=1; counter-- )

What happens if you use "counter++" rather than "counter--"?
for ( int counter=n; counter>=1; counter++ )

While loop solution:
int limit = 10;
int sum = 0;
int count = 1;
while (count <= limit) {
   sum = sum + count;
   count++;
}

Notice the similarities. All the elements of the for loop are also contained in the while loop, just rearranged.  Thus the for loop can always be written as a while loop.

Example: pick a number randomly from 1 to 10.  Repeat until the number is 4.

Random rand = new Random();
while (rand.nextInt(10)+1 != 4) ;

Use the Random class to define a random number generator.  We call it rand.  This class has a method to randomly draw integers from the range 0 (inclusive) to some maximum (exclusive).  So rand.nextInt(10) will return an integer drawn randomly from the range 0 through 9.  I add 1 to it, to get a value from 1 to 10.

Notice that there is no loop body.  Also notice that this is not a very informative thing to do.  See the next example.

Example: Repeat the above experiment 1000 times and determine the average number of picks needed to get a 4.

Random rand = new Random();
int trials = 1000;
int sum = 0;
int picks;
for (int count = 1; count <= trials; count++) {
   picks = 1;
   while (rand.nextInt(10)+1 != 4) {
      picks++;
   }
   sum = sum + picks;
}
double average = (double) sum / trials;

What do you think the average number of picks is?

Example: consider findValue(), a method which exemplifies a number of concepts we've studied this quarter!  It is a method which:

• returns a value,
• has a parameter
• uses assignment statements
• uses selection with an "if" statement
• uses iteration with a "while" loop
• references at least one identifier of each of these kinds: method, local variable, instance variable, parameter.

Explanation of the while loop

First notice this: the while condition references four identifiers:
1. index, which is a local variable
2. count, which is a method of this class
3. theList, which is an instance variable of this class
4. target, which is a parameter of this method

This method will sequentially search the list attempting to match the target value.  I don't know in advance how many loop iterations this will require so I use a "while" loop. If, upon loop termination, index is less than the count of array elements, then the target was matched so return true.

Note that I use this.count() rather than this.theList.length, because the array may not be completely filled.

How the condition for this loop was formed.

Consider the conditions for stopping the search (terminating the loop): either I come to the end of the list or an entry matches the target.

• Call the condition "come to the end of the list", A, and call the condition "entry matches the target", B.
• Thus the search stops with "A or B".
• But the while condition represents condition for staying in the loop, not stopping it!  So this has to be inverted, to "not (A or B)".
• Using DeMorgan's law, "not (A or B)" is the same as "not A and not B".
• Then "not A" represents the phrase "still in the list" and "not B" represents the phrase "entry doesn't match the target".

• Condition "still in the list" is coded as index < this.count().
• Condition "entry doesn't match the target" is coded as this.theList[index] != target.