7.1
Multiple assignment
You can make more than one assignment to the same variable; effect is to
replace the old value with the new.
int bob = 5;
System.out.print(bob);
bob = 7;
System.out.println(bob);
The output of this program is 57, because the first time we print bob his
value is 5, and the second time his value is 7.
This kind of multiple assignment is the reason I described variables as a
container for values. When you assign a value to a variable, you change the
contents of the container, as shown in the figure:
int bob = 5;
bob
5
bob = 7;
bob
5 7
When there are multiple assignments to a variable, it is especially important
to distinguish between an assignment statement and a statement of equality.
Because Java uses the = symbol for assignment, it is tempting to interpret a
statement like a = b as a statement of equality. It is not!
76
Chapter 7. Iteration
First of all, equality is commutative, and assignment is not. For example, in
mathematics if a = 7 then 7 = a. But in Java a = 7; is a legal assignment
statement, and 7 = a; is not.
Furthermore, in mathematics, a statement of equality is true for all time. If
a = b now, then a will always equal b. In Java, an assignment statement can
make two variables equal, but they don’t have to stay that way!
int a = 5;
int b = a;
// a and b are now equal
a = 3;
// a and b are no longer equal
The third line changes the value of a but it does not change the value of b, so
they are no longer equal. In some programming languages a different symbol
is used for assignment, such as <- or :=, to avoid this confusion.
Although multiple assignment is frequently useful, you should use it with
caution. If the values of variables change often, it can make the code difficult
to read and debug.
7.2
Iteration
Computers are often used to automate repetitive tasks. Repeating tasks
without making errors is something that computers do well and people do
poorly.
We have already seen methods, like countdown and factorial, that use
recursion to perform repetition, also called iteration. Java provides language
features that make it easier to write these methods.
The two features we are going to look at are the while statement and the
for statement.
7.3
The while statement
Using a while statement, we can rewrite countdown:
public static void countdown(int n) {
while (n > 0) {
7.3. The while statement
77
System.out.println(n);
n = n-1;
}
System.out.println("Blastoff!");
}
You can almost read a while statement like English. What this means is,
“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 the word ‘Blastoff!”’
More formally, the flow of execution for a while statement is as follows:
1. Evaluate the condition in parentheses, yielding true or false.
2. If the condition is false, exit the while statement and continue execu-
tion at the next statement.
3. If the condition is true, execute the statements between the squiggly-
brackets, and then go back to step 1.
This type of flow is called a loop because the third step loops back around
to the top. The statements inside the loop are called the body of the loop.
If the condition is false the first time through the loop, the statements inside
the loop are never executed.
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. Oth-
erwise 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 if n is
positive.
In other cases it is not so easy to tell:
public static void sequence(int n) {
while (n != 1) {
System.out.println(n);
if (n%2 == 0) {
// n is even
n = n / 2;
78
Chapter 7. Iteration
} else {
// n is odd
n = n*3 + 1;
}
}
}
The condition for this loop is n != 1, so the loop will continue until n is 1,
which will make the condition false.
At each iteration, the program prints 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, or that the program will terminate. For some
particular values of n, we can prove termination. 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 with 16.
Particular values aside, the interesting question is whether we can prove that
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 http://en.wikipedia.
org/wiki/Collatz_conjecture.
7.4
Tables
One of the things loops are good for is generating and printing tabular data.
For example, 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 containing long tables where you
could find the values of various functions. Creating these tables was slow
and boring, and the results were full of errors.
When computers appeared on the scene, one of the initial reactions was,
“This is great! We can use the computers to generate the tables, so there
7.4. Tables
79
will be no errors.” That turned out to be true (mostly), but shortsighted.
Soon thereafter computers were so pervasive that the tables became obsolete.
Well, almost. For some operations, computers use tables of values to get an
approximate answer, and then perform computations to improve the approxi-
mation. 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 division1.
Although a “log table” is not as useful as it once was, it still makes a good
example of iteration. The following program prints a sequence of values in
the left column and their logarithms in the right column:
double x = 1.0;
while (x < 10.0) {
System.out.println(x + "
" + Math.log(x));
x = x + 1.0;
}
The output of this program is
1.0
0.0
2.0
0.6931471805599453
3.0
1.0986122886681098
4.0
1.3862943611198906
5.0
1.6094379124341003
6.0
1.791759469228055
7.0
1.9459101490553132
8.0
2.0794415416798357
9.0
2.1972245773362196
Looking at these values, can you tell what base the log method uses?
Since powers of two are important in computer science, we often want loga-
rithms with respect to base 2. To compute them, we can use the following
formula:
log x = log
2
ex/loge2
(7.1)
Changing the print statement to
1See http://en.wikipedia.org/wiki/Pentium_FDIV_bug.
80
Chapter 7. Iteration
System.out.println(x + "
" + Math.log(x) / Math.log(2.0));
yields
1.0
0.0
2.0
1.0
3.0
1.5849625007211563
4.0
2.0
5.0
2.321928094887362
6.0
2.584962500721156
7.0
2.807354922057604
8.0
3.0
9.0
3.1699250014423126
We can see that 1, 2, 4 and 8 are powers of two, because their logarithms base
2 are round numbers. If we wanted to find the logarithms of other powers of
two, we could modify the program like this:
double x = 1.0;
while (x < 100.0) {
System.out.println(x + "
" + Math.log(x) / Math.log(2.0));
x = x * 2.0;
}
Now instead of adding something to x each time through the loop, which
yields an arithmetic sequence, we multiply x by something, yielding a geo-
metric sequence. The result is:
1.0
0.0
2.0
1.0
4.0
2.0
8.0
3.0
16.0
4.0
32.0
5.0
64.0
6.0
Log tables may not be useful any more, but for computer scientists, knowing
the powers of two is! When you have an idle moment, you should memorize
the powers of two up to 65536 (that’s 216).
7.5. Two-dimensional tables
81
7.5
Two-dimensional tables
A two-dimensional table is a table where you choose a row and a column and
read the value at the intersection. A multiplication table is a good example.
Let’s say you wanted to print a multiplication table for the values from 1 to
6.
A good way to start is to write a simple loop that prints the multiples of 2,
all on one line.
int i = 1;
while (i <= 6) {
System.out.print(2*i + "
");
i = i + 1;
}
System.out.println("");
The first line initializes a variable named i, which is going to act as a counter,
or 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 print
the value 2*i and three spaces. Since we use System.out.print, the output
appears on a single line.
In some environments the output from print gets stored without being dis-
played until println is invoked. If the program terminates, and you forget
to invoke println, you may never see the stored output.
The output of this program is:
2
4
6
8
10
12
So far, so good. The next step is to encapsulate and generalize.
7.6
Encapsulation and generalization
Encapsulation means taking a piece of code and wrapping it up in a method,
allowing you to take advantage of all the things methods are good for. We
have seen two examples of encapsulation, when we wrote printParity in
Section 4.3 and isSingleDigit in Section 6.7.
Generalization means taking something specific, like printing multiples of 2,
and making it more general, like printing the multiples of any integer.
82
Chapter 7. Iteration
Here’s a method that encapsulates the loop from the previous section and
generalizes it to print multiples of n.
public static void printMultiples(int n) {
int i = 1;
while (i <= 6) {
System.out.print(n*i + "
");
i = i + 1;
}
System.out.println("");
}
To encapsulate, all I had to do was add the first line, which declares the
name, parameter, and return type. To generalize, all I had to do was replace
the value 2 with the parameter n.
If I invoke this method with the argument 2, I get the same output as before.
With argument 3, the output is:
3
6
9
12
15
18
and with argument 4, the output is
4
8
12
16
20
24
By now you can probably guess how we are going to print a multiplication
table: we’ll invoke printMultiples repeatedly with different arguments. In
fact, we are going to use another loop to iterate through the rows.
int i = 1;
while (i <= 6) {
printMultiples(i);
i = i + 1;
}
First of all, notice how similar this loop is to the one inside printMultiples.
All I did was replace the print statement with a method invocation.
The output of this program is
1
2
3
4
5
6
2
4
6
8
10
12
3
6
9
12
15
18
4
8
12
16
20
24
5
10
15
20
25
30
6
12
18
24
30
36
7.7. Methods
83
which is a (slightly sloppy) multiplication table. If the sloppiness bothers
you, Java provides methods that give you more control over the format of
the output, but I’m not going to get into that here.
7.7
Methods
In the Section 3.5 I listed some of the reasons methods are useful. Here are
more:
❼ By giving a name to a sequence of statements, you make your program
easier to read and debug.
❼ Dividing a long program into methods allows you to separate parts of
the program, debug them in isolation, and then compose them into a
whole.
❼ Methods facilitate both recursion and iteration.
❼ Well-designed methods are often useful for many programs. Once you
write and debug one, you can reuse it.
7.8
More encapsulation
To demonstrate encapsulation again, I’ll take the code from the previous
section and wrap it up in a method:
public static void printMultTable() {
int i = 1;
while (i <= 6) {
printMultiples(i);
i = i + 1;
}
}
The development process I am demonstrating is called encapsulation and
generalization.
You start by adding code to main or another method.
When you get it working, you extract it and wrap it up in a method. Then
you generalize the method by adding parameters.
84
Chapter 7. Iteration
Sometimes you don’t know when you start writing exactly how to divide the
program into methods. This process lets you design as you go along.
7.9
Local variables
You might wonder how we can use the same variable i in both
printMultiples and printMultTable. Didn’t I say that you can only de-
clare a variable once? And doesn’t it cause problems when one of the methods
changes the value of the variable?
The answer to both questions is “no,” because the i in printMultiples and
the i in printMultTable are not the same variable. They have the same
name, but they do not refer to the same storage location, and changing the
value of one has no effect on the other.
Variables declared inside a method definition are called local variables be-
cause they only exist inside the method. You cannot access a local variable
from outside its “home” method, and you are free to have multiple variables
with the same name, as long as they are not in the same method.
Although it can be confusing, there are good reasons to reuse names. For
example, it is common to use the names i, j and k as loop variables. If you
avoid using them in one method just because you used them somewhere else,
you make the program harder to read.
7.10
More generalization
As another example of generalization, imagine you wanted a program that
would print a multiplication table of any size, not just the 6x6 table. You
could add a parameter to printMultTable:
public static void printMultTable(int high) {
int i = 1;
while (i <= high) {
printMultiples(i);
i = i + 1;
}
}
7.10. More generalization
85
I replaced the value 6 with the parameter high. If I invoke printMultTable
with the argument 7, I get
1
2
3
4
5
6
2
4
6
8
10
12
3
6
9
12
15
18
4
8
12
16
20
24
5
10
15
20
25
30
6
12
18
24
30
36
7
14
21
28
35
42
which is fine, except that I probably want the table to be square (same
number of rows and columns), which means I have to add another parameter
to printMultiples, to specify how many columns the table should have.
I also call this parameter high, demonstrating that different methods can
have parameters with the same name (just like local variables):
public static void printMultiples(int n, int high) {
int i = 1;
while (i <= high) {
System.out.print(n*i + "
");
i = i + 1;
}
newLine();
}
public static void printMultTable(int high) {
int i = 1;
while (i <= high) {
printMultiples(i, high);
i = i + 1;
}
}
Notice that when I added a new parameter, I had to change the first line, and I
also had to change the place where the method is invoked in printMultTable.
As expected, this program generates a square 7x7 table:
1
2
3
4
5
6
7
2
4
6
8
10
12
14
86
Chapter 7. Iteration
3
6
9
12
15
18
21
4
8
12
16
20
24
28
5
10
15
20
25
30
35
6
12
18
24
30
36
42
7
14
21
28
35
42
49
When you generalize a method appropriately, you often find that it has ca-
pabilities you did not plan. For example, you might notice that the multi-
plication table is symmetric, because ab = ba, so all the entries in the table
appear twice. You could save ink by printing only half the table. To do that,
you only have to change one line of printMultTable. Change
printMultiples(i, high);
to
printMultiples(i, i);
and you get
1
2
4
3
6
9
4
8
12
16
5
10
15
20
25
6
12
18
24
30
36
7
14
21
28
35
42
49
I’ll leave it up to you to figure out how it works.
7.11
Glossary
loop: A statement that executes repeatedly while some condition is satisfied.
infinite loop: A loop whose condition is always true.
body: The statements inside the loop.
iteration: One pass through (execution of) the body of the loop, including
the evaluation of the condition.
encapsulate: To divide a large complex program into components (like
methods) and isolate the components from each other (for example,
by using local variables).
7.12. Exercises
87
local variable: A variable that is declared inside a method and that exists
only within that method. Local variables cannot be accessed from out-
side their home method, and do not interfere with any other methods.
generalize: To replace something unnecessarily specific (like a constant
value) with something appropriately general (like a variable or param-
eter).
Generalization makes code more versatile, more likely to be
reused, and sometimes even easier to write.
program development: A process for writing programs. So far we have
seen “incremental development” and “encapsulation and generaliza-
tion”.
7.12
Exercises
Exercise 7.1. public static void main(String[] args) {
loop(10);
}
public static void loop(int n) {
int i = n;
while (i > 0) {
System.out.println(i);
if (i%2 == 0) {
i = i/2;
} else {
i = i+1;
}
}
}
1. Draw a table that shows the value of the variables i and n during the ex-
ecution of loop. The table should contain one column for each variable
and one line for each iteration.
2. What is the output of this program?
88
Chapter 7. Iteration
Exercise 7.2. Let’s say you are given a number, a, and you want to find its
square root. One way to do that is to start with a very rough guess about the
answer, x0, and then improve the guess using the following formula:
x1 = (x0 + a/x0)/2
(7.2)
For example, if we want to find the square root of 9, and we start with x0 = 6,
then x1 = (6 + 9/6)/2 = 15/4 = 3.75, which is closer.
We can repeat the procedure, using x1 to calculate x2, and so on. In this
case, x2 = 3.075 and x3 = 3.00091. So that is converging very quickly on the
right answer(which is 3).
Write a method called squareRoot that takes