Unit 4: Iteration

Unit 4 is about loops, the code that repeats. It covers while loops and for loops, how to choose between them, how to walk through a string one character at a time, how nested loops behave, and how to count how many times a loop runs. Almost every algorithm you write from here on is a loop, so this unit pays off in every unit after it.

4.1 while Loops

A while loop repeats a block of code as long as a condition stays true. The condition is checked before each pass, including the first one. If the condition is false on the first check, the body runs zero times. The three parts you must see are the initialization before the loop, the condition in parentheses, and the update somewhere inside the body that moves the condition toward false.

int count = 1;          // initialization
while (count <= 5)   // condition, checked before each pass
{
    System.out.println(count);
    count++;            // update: without this, the loop never ends
}

Trace it. count starts at 1. The check 1 <= 5 is true, so 1 prints and count becomes 2. The check 2 <= 5 is true, so 2 prints and count becomes 3. This continues until 5 prints and count becomes 6. The check 6 <= 5 is false, so the loop stops. The output is 1, 2, 3, 4, 5. Notice the condition is checked one more time than the body runs.

int i = 1;
while (i <= 5)
{
    System.out.println(i);
    // no update: i stays 1, so the loop never ends
}

Sentinel values

A sentinel value is a special input that ends the loop. It is useful when you do not know in advance how many inputs are coming. The classic pattern reads values until the sentinel appears, and the sentinel itself is not processed.

Scanner input = new Scanner(System.in);
int total = 0;
int num = input.nextInt();
while (num != -1)   // -1 is the sentinel: it ends the loop
{
    total += num;
    num = input.nextInt();
}

The sentinel value -1 is never added to total. Two things must be true for this pattern to work. The first read happens before the loop so the condition has something real to check, and the read repeats at the bottom of the body so the loop can actually reach the sentinel.

4.2 for Loops

A for loop packages the same three parts of a while loop into one header. The initialization runs once at the start, the condition is checked before each pass, and the update runs after each pass, before the condition is checked again. Like a while loop, if the condition is false on the first check, the body runs zero times.

for (int i = 0; i < 5; i++)
{
    System.out.println(i);
}

Trace it. i starts at 0, 0 < 5 is true, so 0 prints and i becomes 1. The body prints 1, 2, 3, 4. After 4 prints, i becomes 5, 5 < 5 is false, and the loop stops. The output is 0, 1, 2, 3, 4. The loop runs 5 times.

for vs while

Use a for loop when you know the number of iterations before the loop starts, which is almost always a counting situation. Use a while loop when the stopping condition depends on something that happens inside the loop, like reading input until a sentinel appears or repeating until a value crosses a threshold. Either loop can do the other's job, but the exam rewards the natural choice, and mixing them up usually means the update or the condition is written awkwardly.

4.3 Developing Algorithms Using Strings

Loop algorithms on strings come in two flavors: traversing, which reads each character in order, and building, which assembles a new string one character at a time. Both use the same index pattern. A string of length n has valid indexes 0 through n − 1, so the loop runs i from 0 while i < word.length(), and word.substring(i, i + 1) grabs the single character at position i.

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

Trace it. word.length() is 3, so i takes the values 0, 1, 2. At i = 0, substring(0, 1) is "c". At i = 1, substring(1, 2) is "a". At i = 2, substring(2, 3) is "t". The output is c, a, t on separate lines. The last valid index is length() − 1, which is why the condition uses < and not <=.

Building strings in a loop

To build a string, start with the empty string and add one piece per pass. Reversing a string is the standard example, and it runs the index backward.

String word = "abc";
String rev = "";
for (int i = word.length() - 1; i >= 0; i--)
{
    rev += word.substring(i, i + 1);
}

Trace it. i starts at 2. substring(2, 3) is "c", so rev becomes "" + "c" = "c". At i = 1, substring(1, 2) is "b", so rev becomes "cb". At i = 0, substring(0, 1) is "a", so rev becomes "cba". Then i becomes −1, the condition fails, and rev is "cba". Starting from "" matters: if rev started as anything else, that leftover text would sit at the front of the answer.

4.4 Nested Iteration

A nested loop is a loop whose body contains another loop. The outer loop controls the big steps and the inner loop runs to completion for every single pass of the outer loop. That last sentence is the whole topic. For each value of the outer variable, the inner loop starts over from its initialization and runs all of its own iterations.

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

Trace it. The outer loop sets row = 1. The inner loop then runs completely: col = 1 prints "11 ", col = 2 prints "12 ", and col = 3 fails the condition. The println moves to the next line. The outer loop sets row = 2 and the inner loop runs completely again, printing "21 " and "22 ". Same for row = 3. The output is:

11 12
21 22
31 32

To count total inner-body executions, multiply the outer count by the inner count: 3 outer passes times 2 inner passes = 6. When the inner bound depends on the outer variable, multiplication no longer works and you must add up the inner counts pass by pass, as in practice question 8.

4.5 Informal Code Analysis

Informal code analysis means reasoning about how many times a loop runs without executing it. The exam does not ask for Big-O notation in this unit. It asks questions like "how many times does the body execute" or "which change makes the loop run fewer times." The method is the same as tracing, but you reason about the pattern instead of listing every pass.

Start by identifying what controls the count. A loop that counts i from 0 to n − 1 runs about n times, no matter what the body does. A nested loop with n outer passes and n inner passes runs about n times n, which is n squared. A loop that halves its value each pass, like the one below, runs far fewer times than a loop that steps by one.

int n = 32;
int steps = 0;
while (n > 1)
{
    n = n / 2;
    steps++;
}
System.out.println(steps);

Trace the halving. n goes 32, 16, 8, 4, 2, 1. The condition n > 1 is true for 32, 16, 8, 4, and 2, so steps reaches 5, then n becomes 1 and the loop stops. Doubling the starting value to 64 would add only one more pass. That is the kind of comparison the exam tests: two loops, same body, and you judge which one does more work.

Confusions That Cost Points

Practice Questions

Original questions written for this guide in the style of the AP exam. Answers and explanations are on the next page, so complete the questions before checking them.

int i = 1;
int sum = 0;
while (i <= 4)
{
    sum += i;
    i += 2;
}
System.out.println(sum);

for (int k = 5; k > 0; k -= 2)
{
    System.out.print(k + " ");
}

String s = "rain";
String result = "";
for (int i = 0; i < s.length(); i++)
{
    result = s.substring(i, i + 1) + result;
}
System.out.println(result);

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

Answer Key

1. B. Trace the loop. i = 1: sum becomes 1, i becomes 3. i = 3: sum becomes 4, i becomes 5. Now 5 <= 4 is false, so the loop stops with sum = 4. A assumes i increases by 1 each pass and adds 1 + 2 + 3, but the update is i += 2. C adds 1 + 2 + 3 + 4, which combines the wrong step with the wrong bound. D is the value of sum after only the first pass, which means the loop was stopped early.

2. A. Trace k. k = 5 prints "5 ", k = 3 prints "3 ", k = 1 prints "1 ", then k becomes −1 and the condition k > 0 is false. The output is "5 3 1 ". B adds an extra "0", which would require the condition to allow k = 0, but k > 0 fails at 0. C starts from the wrong initial value and steps the wrong way. D includes −1, which mistakes the order of the check: the condition is tested before each pass, so −1 never prints.

3. B. Each new character is placed in front of result, so the string builds backward. i = 0 puts "r" first, i = 1 makes "ar", i = 2 makes "iar", i = 3 makes "niar". A is the original string, which would require result = result + char instead of char + result. C scrambles the middle characters, which comes from not tracking the prepend order carefully. D drops the first character, which would happen only if the loop started at i = 1.

4. B. The inner loop runs to completion for every outer pass. The outer loop runs 3 times and the inner loop runs 4 times per outer pass, so count++ executes 3 × 4 = 12 times. A adds 3 + 4 instead of multiplying. C doubles the correct answer, which comes from running the inner loop twice per outer pass by mistake. D counts only the inner passes of a single outer iteration.

5. C. In C, n starts at 1 and increases every pass: 1, 2, 3, and on forever. It never equals 0, so the condition n != 0 never becomes false. A terminates when n reaches 10. B terminates when n reaches 0 (10, 8, 6, 4, 2, 0). D looks suspicious because n-- appears twice, but trace it: n goes 5, 3, 1, −1 and the condition fails at −1, so it terminates. The trap in D is reading only the header.

6. B. List the values of i: 0, 2, 4, 6, 8, 10. That is 6 passes. A gets 5 by forgetting that i starts at 0 and counting only 2 through 10. C divides 10 by 1 instead of by the step of 2. D counts the integers from 0 to 10, which ignores the step of 2 entirely.

7. B. This loop sums the digits of 235. n = 235: total += 5 gives 5, n becomes 23. n = 23: total += 3 gives 8, n becomes 2. n = 2: total += 2 gives 10, n becomes 0, and the loop stops. The answer is 10. A prints n instead of total. C is the digits in reverse order, which is what you would get if the code built a string instead of adding. D is only the first digit extracted, which means the loop stopped after one pass.

8. B. The inner bound depends on the outer variable, so multiplication does not work. Count pass by pass: i = 1 gives 1 inner pass, i = 2 gives 2, i = 3 gives 3, i = 4 gives 4. The total is 1 + 2 + 3 + 4 = 10. A multiplies 4 × 4, which treats the inner bound as fixed at 4 for every outer pass. C multiplies 2 × 4, which has no basis in the code. D counts only the outer passes.

One-Page Recall Check

Say each answer out loud before you look back, and mark the ones you cannot finish. Anything you cannot say out loud yet belongs in your flashcard deck. In Rycal, add those items to the AP Computer Science A deck and let spaced review bring them back over the next few days.

• Explain what happens before each pass of a while loop, and name the three parts every while loop needs.
• Define a sentinel value and explain why the sentinel is never processed by the loop body.
• Describe two ways a loop becomes infinite.
• State what each part of a for loop header does and when it runs.
• Explain the off-by-one error and show how < n and <= n differ when i starts at 0.
• State when to choose a for loop and when to choose a while loop.
• Explain why a loop variable declared in a for header cannot be used after the loop.
• Write the standard string traversal loop from memory and explain why the bound is length() − 1.
• Explain how to reverse a string with a loop and why the result starts as "".
• Explain what the inner loop does on each pass of the outer loop in a nested loop.
• State when to multiply loop counts and when to add them up pass by pass.
• Explain how to compare two loops informally by counting iterations, without Big-O notation.
• Explain why a loop that halves its value each pass runs far fewer times than one that steps by one.

Key terms for this unit

while loop, Initialization, Condition, Update, Infinite loop, Sentinel value, for loop, Off-by-one error, Loop variable scope, String traversal, substring, String building, Empty string, Nested loop, Outer loop, Inner loop, Informal code analysis, Iterations.

About this guide. Written for Rycal and aligned to the College Board AP Computer Science A course framework, Unit 4. All questions and explanations are original Rycal writing. Rycal is independent and is not affiliated with or endorsed by the College Board.