Nested Iteration

A track coach plans two practice rounds, and in each round the runners do three laps. Writing the plan out by hand, you would write “Round 1”, then lap 1, lap 2, lap 3, then “Round 2”, then lap 1, lap 2, lap 3 again. Notice the shape: there is a repeated task (a round), and inside each repetition there is another repeated task (the laps). A single loop from Topics 2.7 and 2.8 can repeat the rounds, but each round itself needs repetition too.

Java handles this the way you would expect once you remember one fact: a loop’s body can hold any statements at all, and a loop is a statement. So the body of one loop can contain a whole second loop.

A loop that appears inside the body of another loop is called a nested loop, and using loops this way is called nested iteration. The loop on the outside is the outer loop; the loop inside its body is the inner loop. The outer loop’s body is everything between its braces, which here is a print statement and the entire inner loop.

for (int round = 1; round <= 2; round++)
{
    System.out.println("Round " + round);
    for (int lap = 1; lap <= 3; lap++)
    {
        System.out.println("  lap " + lap);
    }
}

Round 1
  lap 1
  lap 2
  lap 3
Round 2
  lap 1
  lap 2
  lap 3

Any kind of loop can be nested inside any kind of loop. The next program is the same shape built from two while loops, and it prints something on one line for each set of an exercise.

int set = 1;
while (set <= 3)
{
    System.out.print("Set " + set + ": ");
    int rep = 1;
    while (rep <= 4)
    {
        System.out.print("#");
        rep++;
    }
    System.out.println();
    set++;
}

Set 1: ####
Set 2: ####
Set 3: ####

public class SameName
{
    public static void main(String[] args)
    {
        for (int i = 1; i <= 3; i++)
        {
            for (int i = 1; i <= 2; i++)
            {
                System.out.println("Hi");
            }
        }
    }
}

SameName.java:7: error: variable i is already defined in method main(String[])

for (int i = 1; i <= 3; i++)
{
    for (int j = 1; j <= 2; j++)
    {
        System.out.println(i + " " + j);
    }
}

for (int song = 1; song <= 2; song++)
{
    System.out.println("Song " + song);
    for (int verse = 1; verse <= 2; verse++)
    {
        System.out.println("verse " + verse);
    }
    System.out.println("chorus");
}

Song 1
verse 1
verse 2
chorus
Song 2
verse 1
verse 2
chorus

for (int floor = 1; floor <= 4; floor++)
{
    System.out.println("Floor " + floor);
    for (int room = 1; room <= 3; room++)
    {
        System.out.println("room " + room);
    }
}

You now know what runs in a nested loop. The harder question is in what order. When the outer loop has done one iteration and the inner loop has done one, which goes next? Getting this right is the whole skill of tracing nested loops.

Think of a car’s odometer. The rightmost digit rolls through 0, 1, 2, … 9, and only after it has gone all the way around does the digit to its left move up by one. Then the rightmost digit starts over from 0. The inner loop is the fast digit; the outer loop is the slow one. (The analogy stops there: an odometer digit always has ten values, but an inner loop can run any number of times, even a different number each time, as you will see in 2.11.4.)

Here is the rule in Java terms. Each time the outer loop’s body runs, Java reaches the inner loop as a brand-new statement:

1. The inner loop starts from the beginning. For a for loop, that means its initialization runs again, so the inner variable starts over.
2. The inner loop runs all of its iterations until its condition is false.
3. Only then does Java continue with the rest of the outer loop’s body, and after that the outer loop does its update and checks its own condition.

The loops never take turns one step at a time. The outer loop’s variable stays the same value the whole time the inner loop is running.

for (int outer = 1; outer <= 3; outer++)
{
    for (int inner = 1; inner <= 2; inner++)
    {
        System.out.println(outer + " " + inner);
    }
}

1 1
1 2
2 1
2 2
3 1
3 2

Because the inner loop runs completely every time, you can count how many times the inner body runs: if the outer loop runs 3 times and the inner loop runs 2 times on each of those, the inner body runs 3 × 2 = 6 times. The next example lets the program do that counting.

int count = 0;
for (int team = 1; team <= 4; team++)
{
    for (int game = 1; game <= 3; game++)
    {
        count++;
    }
}
System.out.println("Games played: " + count);

Games played: 12

int count = 0;
int team = 1;
int game = 1;
while (team <= 4)
{
    while (game <= 3)
    {
        count++;
        game++;
    }
    team++;
}
System.out.println("Games played: " + count);

Games played: 3

int count = 0;
int team = 1;
while (team <= 4)
{
    int game = 1;
    while (game <= 3)
    {
        count++;
        game++;
    }
    team++;
}
System.out.println("Games played: " + count);

for (int a = 1; a <= 2; a++)
{
    for (int b = 3; b >= 1; b--)
    {
        System.out.println(a + "-" + b);
    }
}

1-3
1-2
1-1
2-3
2-2
2-1

int count = 0;
int week = 0;
while (week < 5)
{
    for (int day = 1; day <= 4; day++)
    {
        count++;
    }
    week++;
}
System.out.println(count);

Nested loops are the natural tool whenever something has rows and columns: seats in a theater, a calendar page, a grid of tiles, or a picture drawn with characters. Pattern printing is a favorite way to practice reading nested loops, because the output shows the structure of the loops directly.

The trick depends on the difference between the two print statements from Topic 1.3. System.out.print prints and stays on the same line, so the next thing printed appears right after it. System.out.println() with nothing in the parentheses prints nothing and just ends the current line, so the next output starts on a new line.

Put those together with nested loops and you get a plan:

• The inner loop prints one row, one column at a time, using print so everything stays on that row.
• After the inner loop ends, but still inside the outer loop’s body, a println() ends the row.
• The outer loop repeats this once per row.

So the outer loop decides how many rows there are, and the inner loop decides how many columns are in each row.

for (int row = 1; row <= 3; row++)
{
    for (int col = 1; col <= 5; col++)
    {
        System.out.print("*");
    }
    System.out.println();
}

*****
*****
*****

The inner body does not have to print the same thing every time. It can print one of the loop variables, and which one you choose changes the pattern completely.

for (int row = 1; row <= 3; row++)
{
    for (int col = 1; col <= 5; col++)
    {
        System.out.print(col);
    }
    System.out.println();
}

12345
12345
12345

for (int row = 1; row <= 3; row++)
{
    for (int col = 1; col <= 5; col++)
    {
        System.out.print(row);
    }
    System.out.println();
}

11111
22222
33333

for (int row = 1; row <= 2; row++)
{
    for (int col = 1; col <= 4; col++)
    {
        System.out.print("*");
        System.out.println();
    }
}

*
*
*
*
*
*
*
*

for (int row = 1; row <= 2; row++)
{
    for (int col = 1; col <= 4; col++)
    {
        System.out.print("*");
    }
    System.out.println();
}

****
****

for (int r = 1; r <= 2; r++)
{
    for (int c = 1; c <= 4; c++)
    {
        System.out.print(r * c);
    }
    System.out.println();
}

1234
2468

for (int row = 1; row <= 4; row++)
{
    for (int col = 1; col <= 3; col++)
    {
        System.out.print("#");
    }
}

for (int row = 1; row <= 4; row++)
{
    for (int col = 1; col <= 3; col++)
    {
        System.out.print("#");
    }
    System.out.println();
}

###
###
###
###

So far, every inner loop ran the same number of times on every pass. That gives rectangles. But many real tasks change from row to row: in a seating chart for a stadium section, the first row might have 1 seat, the next 2, and so on; a staircase gets one step longer each line.

The outer loop’s variable can help here. Remember from 2.11.2 that while the inner loop runs, the outer variable holds steady. That means the inner loop’s condition can use the outer variable, and on each pass of the outer loop the inner loop gets a different stopping point. When the outer variable is 1, the inner loop might run once; when it is 4, four times.

for (int row = 1; row <= 4; row++)
{
    for (int star = 1; star <= row; star++)
    {
        System.out.print("*");
    }
    System.out.println();
}

*
**
***
****

for (int row = 4; row >= 1; row--)
{
    for (int col = 1; col <= row; col++)
    {
        System.out.print(col);
    }
    System.out.println();
}

1234
123
12
1

for (int row = 1; row <= 4; row++)
{
    for (int star = 1; star < row; star++)
    {
        System.out.print("*");
    }
    System.out.println();
}

*
**
***

for (int i = 1; i <= 3; i++)
{
    for (int j = i; j <= 3; j++)
    {
        System.out.print(j);
    }
    System.out.println();
}

123
23
3

int count = 0;
for (int row = 1; row <= 4; row++)
{
    for (int k = 1; k < row; k++)
    {
        count++;
    }
}
System.out.println(count);

In Topic 2.10 you used one loop to look at each character of a string. Some questions need two loops: “Does any letter appear more than once in this word?” To answer it, you have to compare every letter with every letter that comes after it. The outer loop picks a letter; the inner loop walks through the letters after it. This program combines everything in the chapter: an inner loop that runs completely for each outer pass, an inner starting value that depends on the outer variable, and an if statement (Topic 2.3) inside the inner body.

public class RepeatedLetters
{
    public static void main(String[] args)
    {
        String word = "level";
        int pairs = 0;
        for (int i = 0; i < word.length(); i++)
        {
            String first = word.substring(i, i + 1);
            for (int j = i + 1; j < word.length(); j++)
            {
                String second = word.substring(j, j + 1);
                if (first.equals(second))
                {
                    System.out.println(first + " at " + i + " and " + j);
                    pairs++;
                }
            }
        }
        System.out.println("Matching pairs: " + pairs);
    }
}

l at 0 and 4
e at 1 and 3
Matching pairs: 2

• A nested loop is a loop inside the body of another loop. Any loop type can be nested in any other, and the inner loop is just one more statement in the outer loop’s body.
• Each time the outer loop’s body runs, the inner loop starts over and completes all of its iterations before the outer loop continues. The inner variable changes fastest; the outer variable stays the same while the inner loop runs.
• If the inner loop runs the same number of times on every pass, the inner body runs (outer passes) × (inner passes) times. If its count changes, add up the count for each pass.
• To print a grid, the inner loop prints one row with print, a println() after the inner loop ends the row, and the outer loop repeats for each row.
• When the inner loop’s condition or starting value uses the outer variable, each row can be a different length, as in a triangle.
• Watch for a reused loop variable name (a compile error), an inner while counter set before the outer loop (it never restarts), a misplaced println(), and off-by-one inner conditions.

for (int row = 1; row <= 4; row++)
{
    int sum = 0;
    for (int n = 1; n <= row; n++)
    {
        sum += n;
    }
    System.out.println("Row " + row + ": " + sum);
}

Row 1: 1
Row 2: 3
Row 3: 6
Row 4: 10

1
22
333

for (int row = 1; row <= 3; row++)
{
    for (int col = 1; /* condition */; col++)
    {
        System.out.print(/* value */);
    }
    System.out.println();
}

int row = 1;
int star = 1;
while (row <= 3)
{
    while (star <= row)
    {
        System.out.print("*");
        star++;
    }
    System.out.println();
    row++;
}

*
*
*

int row = 1;
while (row <= 3)
{
    int star = 1;
    while (star <= row)
    {
        System.out.print("*");
        star++;
    }
    System.out.println();
    row++;
}

*
**
***

for (int a = 1; a <= 2; a++)
{
    for (int b = 1; b <= 2; b++)
    {
        System.out.println(a + "" + b);
    }
}

int count = 0;
for (int a = 1; a <= 4; a++)
{
    for (int b = 1; b <= 4; b++)
    {
        if (a + b == 5)
        {
            count++;
        }
    }
}
System.out.println(count);

String word = "cat";
for (int i = 0; i < word.length(); i++)
{
    for (int j = 0; j <= i; j++)
    {
        System.out.print(word.substring(i, i + 1));
    }
    System.out.println();
}

c
aa
ttt

• I can point to the outer loop and the inner loop in a nested loop and say what is in the outer loop's body. Reread
• I can explain why reusing the outer loop's variable name for the inner loop does not compile. Reread
• I can explain why the inner loop finishes all its iterations before the outer loop moves on, and trace the order of the output. Reread
• I can count how many times an inner loop body runs, and spot an inner while counter that never starts over. Reread
• I can predict the rows and columns a nested loop prints, and say where println() belongs. Reread
• I can trace an inner loop whose condition or starting value uses the outer loop's variable. Reread