Nested Iteration: Study Guide (Computer Science A 2.11)

A loop inside a loop

Many problems have two dimensions: the rows and columns of a pattern, every pair of numbers from two ranges, every letter compared with every other letter. To handle them you put one loop inside the body of another. Nested iteration statements are iteration statements that appear in the body of another iteration statement.

The rule that governs everything in this topic is:

When a loop is nested inside another loop, the inner loop must complete all its iterations before the outer loop can continue to its next iteration.

For each single pass of the outer loop, the inner loop starts, runs all the way through, and finishes. On the outer loop’s next pass the inner loop starts again from the beginning.

Rows and columns

The simplest picture is a grid. The outer loop selects the row; the inner loop visits each column in that row.

public class Rectangle {
    public static void main(String[] args) {
        for (int row = 1; row <= 3; row++) {
            for (int col = 1; col <= 4; col++) {
                System.out.print("*");
            }
            System.out.println();
        }
    }
}

Output:

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

For each of the 3 values of row, the inner loop prints 4 stars, and then the println after the inner loop ends the row. The * statement runs 3 x 4 = 12 times, and the println runs only 3 times because it is in the outer loop’s body, not the inner one.

When the inner bound depends on the outer variable

If the inner loop’s limit uses the outer variable, the rows have different lengths.

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

Output:

*
**
***
****

Row 1 runs the inner loop once, row 2 runs it twice, and so on. The star statement runs 1 + 2 + 3 + 4 = 10 times. For a triangle with n rows the total is 1 + 2 + … + n = n(n + 1) / 2.

Tables and combinations

A nested loop can produce a table of values:

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

Output:

1 2 3
2 4 6
3 6 9

It can also test every combination of two values. Counting the pairs of whole numbers from 1 to 9 that add up to 10:

int pairs = 0;
for (int a = 1; a <= 9; a++) {
    for (int b = 1; b <= 9; b++) {
        if (a + b == 10) {
            pairs++;
        }
    }
}
System.out.println(pairs);

Output:

9

There are 81 combinations (9 x 9). For each a from 1 to 9 there is exactly one b (10 - a), so 9 pairs satisfy the test. If you only want each pair once, with a < b, start the inner loop at a + 1: for (int b = a + 1; b <= 9; b++). That gives (1, 9), (2, 8), (3, 7) and (4, 6): 4 pairs.

Counting the executions of the inner body

For any nested loop you can find how often the innermost statement runs.

Loop structure (outer, inner)	Count
i from 0 to 3, j from 0 to 2 (independent)	4 x 3 = 12
i from 1 to 4, j from 1 to i	1 + 2 + 3 + 4 = 10
i from 0 to 3, j from i to 3	4 + 3 + 2 + 1 = 10
i from 0 to 3, j from i + 1 to 3	3 + 2 + 1 + 0 = 6

If the inner count is the same for every outer pass, multiply. If it changes, list the inner count for each outer value and add.

The inner variable must start again

With for loops, the inner variable is declared in the inner header, so it is re-initialised on every outer pass automatically. With while loops you must do it yourself, and forgetting is a classic mistake.

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

Output:

XXX

In the first pass col runs from 1 to 4. On the second pass col is still 4, so col <= 3 is false at once, the inner loop does nothing, and only an empty line is printed. The initial condition for the inner loop (col equal to 1) is no longer true. The fix is to set col = 1; inside the outer loop, just before the inner loop:

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

Output:

XXX
XXX
XXX

Declaring col inside the outer loop re-creates it on every pass, giving the inner loop its starting value again.

Worked example 1: counting executions

Question. For n = 4, how many times does count++ run in each segment?

public class Counts {
    public static void main(String[] args) {
        int n = 4;
        int a = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a++;
            }
        }
        int b = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                b++;
            }
        }
        int c = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                c++;
            }
        }
        System.out.println(a + " " + b + " " + c);
    }
}

Output:

16 10 6

Segment 1. The inner loop always runs n = 4 times, and the outer loop runs 4 times: 4 x 4 = 16.

Segment 2. For i = 0, 1, 2, 3 the inner loop runs i + 1 times: 1, 2, 3, 4. The total is 1 + 2 + 3 + 4 = 10.

Segment 3. The inner loop starts at i + 1, so it runs n - 1 - i times: 3, 2, 1, 0. The total is 3 + 2 + 1 + 0 = 6. When i is 3 the inner loop starts at 4, and 4 < 4 is false, so it runs zero times.

i	Segment 1 inner passes	Segment 2 inner passes	Segment 3 inner passes
0	4	1	3
1	4	2	2
2	4	3	1
3	4	4	0
total	16	10	6

Check. Segment 2 and segment 3 together cover the 16 combinations of Segment 1: they split the grid into the part on or below the diagonal (10 cells) and the part strictly above it (6 cells), and 10 + 6 = 16.

Worked example 2: tracing nested loops with selection

Question. What does the following print, and how many pairs are found?

public class Pairs {
    public static void main(String[] args) {
        int count = 0;
        for (int a = 1; a <= 4; a++) {
            for (int b = a; b <= 4; b++) {
                if ((a + b) % 3 == 0) {
                    count++;
                    System.out.print("(" + a + "," + b + ") ");
                }
            }
        }
        System.out.println();
        System.out.println(count);
    }
}

Output:

(1,2) (2,4) (3,3)
3

Trace.

a	b values	a + b	(a + b) % 3 == 0?
1	1, 2, 3, 4	2, 3, 4, 5	only b = 2 (sum 3)
2	2, 3, 4	4, 5, 6	only b = 4 (sum 6)
3	3, 4	6, 7	only b = 3 (sum 6)
4	4	8	none

Pairs found, in the order they are visited: (1,2), (2,4), (3,3). Count = 3. Check. The inner loop starts at a, so the pairs satisfy b >= a and each unordered pair is visited once (with equal values allowed). The total number of pairs examined is 4 + 3 + 2 + 1 = 10, of which 3 have a sum divisible by 3.

How this appears in exam questions

Nested loops appear as output questions, counting questions and code-writing tasks. For output, find where print and println sit: a println after the inner loop and inside the outer loop ends each row. For counting, write one line per outer value showing how many times the inner loop runs, and add the lines if the inner bound changes. For code-writing, decide first which loop controls the rows and which the columns, then decide whether the inner loop starts at 0, at the outer variable, or at the outer variable plus 1, depending on whether equal pairs and repeated pairs are wanted. The same structure returns in Unit 4, where the outer loop walks the rows of a 2D array and the inner loop walks the columns, so the picture in Figure 1 is worth learning well now.

Common misconceptions

• “The two loops take turns, one step each.” The inner loop runs completely for each single step of the outer loop.
• “The body runs outer + inner times.” For independent bounds it runs outer x inner times.
• “println after the inner loop runs once in total.” It runs once per outer iteration, because it is in the outer loop’s body.
• “The inner variable keeps its value between outer passes.” With a for loop it is re-created and re-initialised each time. With a while loop it keeps its value unless you reset it.
• “A triangle’s inner bound is a fixed number.” Its bound uses the outer variable, so the inner loop runs a different number of times for each row.
• “The inner loop can never run zero times.” It can: if its start already fails the test (for example j = i + 1 when i is the last value).
• “The output pattern only depends on the inner loop.” Both loops, and the position of the println, shape the output.

Where this leads

Nested loops are the engine of 2D array traversal in Topics 4.11 to 4.13 (the rows-and-columns picture here becomes a 2D array), and of the sorting algorithms in Topic 4.15. In Topic 2.12 you will count executions more formally to compare how fast the work grows. Try the practice questions, recap with the revision notes and tick off the checklist. Then read the Topic 2.12 study guide. For single loops, revisit the Topic 2.8 study guide.