Introduction to Nested Iteration

In the previous chapters, we learned how to use while loops and for loops to repeat a block of code. But what happens if the task we need to repeat is itself a repetition? This is where nested iteration comes in.

Nested iteration is simply placing one loop inside another loop. This is a powerful tool used for creating grids, processing tables of data, and solving complex patterns. Don't worry if it feels a bit "loopy" at first—once you understand the relationship between the outer loop and the inner loop, you'll be able to trace even the most complex code segments with ease!

The Structure of Nested Loops

In a nested loop, we have two main parts:

1. The Outer Loop: This loop controls how many times the entire inner process repeats.
2. The Inner Loop: This loop must finish all of its iterations for every single iteration of the outer loop.

Think of it like a clock. The hour hand is like the outer loop, and the minute hand is like the inner loop. For every one hour that passes (one outer loop step), the minute hand must go around 60 times (all inner loop steps).

A Standard "For" Loop Example

Consider this code segment:

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

Tracing the Execution:

Let's follow the variables \(i\) (outer) and \(j\) (inner):

  • Outer Loop starts: \(i = 1\)
    • Inner Loop runs: \(j = 1\). Output: 1,1
    • Inner Loop runs: \(j = 2\). Output: 1,2
    • Inner loop finishes.
  • Outer Loop increments: \(i = 2\)
    • Inner Loop runs: \(j = 1\). Output: 2,1
    • Inner Loop runs: \(j = 2\). Output: 2,2
    • Inner loop finishes.
  • Outer Loop increments: \(i = 3\)
    • Inner Loop runs: \(j = 1\). Output: 3,1
    • Inner Loop runs: \(j = 2\). Output: 3,2
    • Inner loop finishes.

Final Output: 1,1 1,2 2,1 2,2 3,1 3,2

Key Concept: Total Iterations

One of the most common questions on the AP Exam involves informal run-time analysis—essentially counting how many times a statement executes.

If the outer loop runs \(n\) times and the inner loop runs \(m\) times, the code inside the inner loop will execute a total of \(n \times m\) times.

Quick Example: If you have an outer loop running 5 times and an inner loop running 10 times, the code inside will run \(5 \times 10 = 50\) times.

Dependent Nested Loops (The "Triangle" Pattern)

In many algorithms, the inner loop's range depends on the current value of the outer loop's variable. This is very common when processing Strings or patterns.

Example:
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print("*");
    }
    System.out.println();
}

In this case, notice that the inner loop condition is \(j \leq i\). This means the inner loop runs more times as \(i\) increases!

  • When \(i = 1\), inner runs 1 time. Output: *
  • When \(i = 2\), inner runs 2 times. Output: **
  • When \(i = 3\), inner runs 3 times. Output: ***
  • When \(i = 4\), inner runs 4 times. Output: ****

Common Pitfalls to Avoid

1. Using the same variable: Never use the same counter variable for both loops (e.g., using \(i\) for both). This will confuse the program and likely lead to an infinite loop or logic error.

2. Miscounting iterations: Watch out for the difference between \(<\) and \(\leq\). A loop from 0 to 5 using \(<\) runs 5 times, but using \(\leq\) runs 6 times.

3. Forgetting the "Reset": Remember that every time the outer loop moves to its next step, the inner loop starts over completely from its initial value.

Informal Run-Time Analysis

On the AP Computer Science A exam, you will be asked to compare algorithms informally. For nested loops, you should focus on how many times the "inner-most" statement executes.

Consider two algorithms to print a grid of size \(n \times n\):

Algorithm A: A single loop running \(n^2\) times.
Algorithm B: A nested loop where the outer runs \(n\) times and the inner runs \(n\) times.

In terms of statement execution counts, both perform the same amount of work: \(n \times n = n^2\).

Quick Review

  • Nested iteration is a loop inside a loop.
  • For each iteration of the outer loop, the inner loop runs all its iterations.
  • The total number of executions is the product of the number of iterations of each loop (if they are independent).
  • Nested loops are the standard way to represent and traverse 2D structures (which you will see more of in Unit 4).

Pro-Tip for the Exam: When tracing nested loops on paper, always keep a table with columns for the outer variable, the inner variable, and the output. This prevents you from losing your place!