Chapter 7  Loops

Computers are often used to automate repetitive tasks. Repeating tasks without making errors is something that computers do well and people do poorly.

Running the same code multiple times is called iteration. We have seen methods, like countdown and factorial, that use recursion to iterate. Although recursion is elegant and powerful, it takes some getting used to. Java provides language features that make iteration much easier: the while and for statements.

7.1  The while statement

Using a while statement, we can rewrite countdown like this:

You can almost read the while statement like English: “While n is greater than zero, print the value of n and then reduce the value of n by 1. When you get to zero, print Blastoff!”

The expression in parentheses is called the condition. The statements in braces are called the body. The flow of execution for a while statement is:

1. Evaluate the condition, yielding true or false.
2. If the condition is false, skip the body and go to the next statement.
3. If the condition is true, execute the body and go back to step 1.

This type of flow is called a loop, because the last step loops back around to the first.

The body of the loop should change the value of one or more variables so that, eventually, the condition becomes false and the loop terminates. Otherwise the loop will repeat forever, which is called an infinite loop. An endless source of amusement for computer scientists is the observation that the directions on shampoo, “Lather, rinse, repeat,” are an infinite loop.

In the case of countdown, we can prove that the loop terminates when n is positive. But in general, it is not so easy to tell whether a loop terminates. For example, this loop continues until n is 1 (which makes the condition false):

Each time through the loop, the program displays the value of n and then checks whether it is even or odd. If it is even, the value of n is divided by two. If it is odd, the value is replaced by 3n+1. For example, if the starting value (the argument passed to sequence) is 3, the resulting sequence is 3, 10, 5, 16, 8, 4, 2, 1.

Since n sometimes increases and sometimes decreases, there is no obvious proof that n will ever reach 1 and that the program will ever terminate. For some values of n, we can prove that it terminates. For example, if the starting value is a power of two, then the value of n will be even every time through the loop until we get to 1. The previous example ends with such a sequence, starting when n is 16.

The hard question is whether this program terminates for all values of n. So far, no one has been able to prove it or disprove it! For more information, see https://en.wikipedia.org/wiki/Collatz_conjecture.

7.2  Generating tables

Loops are good for generating and displaying tabular data. Before computers were readily available, people had to calculate logarithms, sines and cosines, and other common mathematical functions by hand. To make that easier, there were books of tables where you could look up values of various functions. Creating these tables by hand was slow and boring, and the results were often full of errors.

When computers appeared on the scene, one of the initial reactions was: “This is great! We can use a computer to generate the tables, so there will be no errors.” That turned out to be true (mostly), but shortsighted. Not much later, computers were so pervasive that printed tables became obsolete.

Even so, for some operations, computers use tables of values to get an approximate answer, and then perform computations to improve the approximation. In some cases, there have been errors in the underlying tables, most famously in the table the original Intel Pentium used to perform floating-point division (see https://en.wikipedia.org/wiki/Pentium_FDIV_bug).

Although a “log table” is not as useful as it once was, it still makes a good example of iteration. The following loop displays a table with a sequence of values in the left column and their logarithms in the right column:

The output of this program is:

Math.log computes natural logarithms, that is, logarithms base e. For computer science applications, we often want logarithms with respect to base 2. To compute them, we can apply this equation:

We can modify the loop as follows:

And here are the results:

Each time through the loop, we add one to x, so the result is an arithmetic sequence. If we multiply x by something instead, we get a geometric sequence:

The first line stores Math.log(2) in a final variable to avoid computing that value over and over again. The last line multiplies x by 2. The result is:

This table shows the powers of two and their logarithms, base 2. Log tables may not be useful anymore, but for computer scientists, knowing the powers of two helps a lot!

7.3  Encapsulation and generalization

In Section 6.2, we presented a way of writing programs called incremental development. In this section we present another program development process called “encapsulation and generalization”. The steps are:

1. Write a few lines of code in main or another method, and test them.
2. When they are working, wrap them in a new method, and test again.
3. If it’s appropriate, replace literal values with variables and parameters.

The second step is called encapsulation; the third step is generalization.

To demonstrate this process, we’ll develop methods that display multiplication tables. Here is a loop that displays the multiples of two, all on one line:

The first line initializes a variable named i, which is going to act as a loop variable: as the loop executes, the value of i increases from 1 to 6; when i is 7, the loop terminates.

Each time through the loop, we display the value 2 * i padded with spaces so it’s four characters wide. Since we use System.out.printf, the output appears on a single line.

After the loop, we call println to print a newline and complete the line. Remember that in some environments, none of the output is displayed until the line is complete.

The output of the code so far is:

The next step is to “encapsulate” this code in a new method. Here’s what it looks like:

Next we replace the constant value, 2, with a parameter, n. This step is called “generalization” because it makes the method more general (less specific).

Invoking this method with the argument 2 yields the same output as before. With the argument 3, the output is:

And with argument 4, the output is:

By now you can probably guess how we are going to display a multiplication table: we’ll invoke printRow repeatedly with different arguments. In fact, we’ll use another loop to iterate through the rows.

And the output looks like this:

The format specifier \%4d in printRow causes the output to align vertically, regardless of whether the numbers are one or two digits.

Finally, we encapsulate the second loop in a method:

One of the challenges of programming, especially for beginners, is figuring out how to divide up a program into methods. The process of encapsulation and generalization allows you to design as you go along.

7.4  More generalization

The previous version of printTable always displays six rows. We can generalize it by replacing the literal 6 with a parameter:

Here is the output with the argument 7:

That’s better, but it still has a problem: it always displays the same number of columns. We can generalize more by adding a parameter to printRow:

Now printRow takes two parameters: n is the value whose multiples should be displayed, and cols is the number of columns. Since we added a parameter to printRow, we also have to change the line in printTable where it is invoked:

When this line executes, it evaluates rows and passes the value, which is 7 in this example, as an argument. In printRow, this value is assigned to cols. As a result, the number of columns equals the number of rows, so we get a square 7x7 table:

When you generalize a method appropriately, you often find that it has capabilities you did not plan. For example, you might notice that the multiplication table is symmetric; since ab = ba, all the entries in the table appear twice. You could save ink by printing half of the table, and you would only have to change one line of printTable:

In words, the length of each row is the same as its row number. The result is a triangular multiplication table.

Generalization makes code more versatile, more likely to be reused, and sometimes easier to write.

7.5  The for statement

The loops we have written so far have several elements in common. They start by initializing a variable, they have a condition that depends on that variable, and inside the loop they do something to update that variable. This type of loop is so common that there is another statement, the for loop, that expresses it more concisely.

For example, we could rewrite printTable like this:

for loops have three components in parentheses, separated by semicolons: the initializer, the condition, and the update.

1. The initializer runs once at the very beginning of the loop.
2. The condition is checked each time through the loop. If it is false, the loop ends. Otherwise, the body of the loop is executed (again).
3. At the end of each iteration, the update runs, and we go back to step 2.

The for loop is often easier to read because it puts all the loop-related statements at the top of the loop.

There is one difference between for loops and while loops: if you declare a variable in the initializer, it only exists inside the for loop. For example, here is a version of printRow that uses a for loop:

The last line tries to display i (for no reason other than demonstration) but it won’t work. If you need to use a loop variable outside the loop, you have to declare it outside the loop, like this:

Assignments like i = i + 1 don’t often appear in for loops, because Java provides a more concise way to add and subtract by one. Specifically, ++ is the increment operator; it has the same effect as i = i + 1. And -- is the decrement operator; it has the same effect as i = i - 1.

If you want to increment or decrement a variable by an amount other than 1, you can use += and -=. For example, i += 2 increments i by 2.

7.6  The do-while loop

The while and for statements are pretest loops; that is, they test the condition first and at the beginning of each pass through the loop.

Java also provides a posttest loop: the do-while statement. This type of loop is useful when you need to run the body of the loop at least once.

For example, in Section 5.7 we used the return statement to avoid reading invalid input from the user. We can use a do-while loop to keep reading input until it’s valid:

Although this code looks complicated, it is essentially only three steps:

1. Display a prompt.
2. Check the input; if invalid, display an error and start over.
3. Read the input.

The code uses a flag variable, okay, to indicate whether we need to repeat the loop body. If hasNextDouble() returns false, we consume the invalid input by calling next(). We then display an error message via System.err. The loop terminates when hasNextDouble() return true.

7.7  Break and continue

Sometimes neither a pretest nor a posttest loop will provide exactly what you need. In the previous example, the “test” needed to happen in the middle of the loop. As a result, we used a flag variable and a nested if-else statement.

A simpler way to solve this problem is to use a break statement. When a program reaches a break statement, it exits the current loop.

Using true as a conditional in a while loop is an idiom that means “loop forever”, or in this case “loop until you get to a break statement.”

In addition to the break statement, which exits the loop, Java provides a continue statement that moves on to the next iteration. For example, the following code reads integers from the keyboard and computes a running total. The continue statement causes the program to skip over any negative values.

Although break and continue statements give you more control of the loop execution, they can make code difficult to understand and debug. Use them sparingly.

7.8  Vocabulary

iteration:

Executing a sequence of statements repeatedly.

loop:

A statement that executes a sequence of statements repeatedly.

loop body:

The statements inside the loop.

infinite loop:

A loop whose condition is always true.

program development:

A process for writing programs. So far we have seen “incremental development” and “encapsulation and generalization”.

encapsulate:

To wrap a sequence of statements in a method.

generalize:

To replace something unnecessarily specific (like a constant value) with something appropriately general (like a variable or parameter).

loop variable:

A variable that is initialized, tested, and updated in order to control a loop.

increment:

Increase the value of a variable.

decrement:

Decrease the value of a variable.

pretest loop:

A loop that tests the condition before each iteration.

posttest loop:

A loop that tests the condition after each iteration.

7.9  Exercises

The code for this chapter is in the ch07 directory of ThinkJavaCode. See page ?? for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.

If you have not already read Appendix A.5, now might be a good time. It describes Checkstyle, a tool that analyzes many aspects of your source code.