3.8 Iteration

What you need to know

• Iteration (looping) is the third building block of algorithms. The code inside the loop is the loop body.
• REPEAT n TIMES { body } runs the body exactly n times.
• REPEAT UNTIL (condition) { body } checks the condition before each pass. If the condition is already true at the start, the body runs zero times. Otherwise it runs, then re-checks, until the condition becomes true.
• FOR EACH item IN list { body } runs the body once per element, in order, with item holding the current element (covered more in 3.10).
• An infinite loop occurs when a REPEAT UNTIL condition can never become true. The exam asks you to spot the variable that never changes.
• The typical pattern: initialize a counter or accumulator before the loop, update it inside, and use it after. Tracing = table with one row per iteration.
• Loop variables retain their final value after the loop ends. If a REPEAT UNTIL stops when i = 5, i is 5 afterward.

Worked example

i ← 1
sum ← 0
REPEAT UNTIL (i > 4)
{
    sum ← sum + i
    i ← i + 1
}
DISPLAY(sum)
DISPLAY(i)

Output: 10 5. Four iterations; i ends at 5, not 4.

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• REPEAT UNTIL checks its condition before each iteration, including the first. If the condition is already true, the body runs zero times. (Some real languages have do-while loops that run the body at least once; AP pseudocode's REPEAT UNTIL does not.)
• The condition is a stopping condition: the loop continues while it's false and stops when it becomes true. Students used to "while" loops must mentally negate. REPEAT UNTIL (i > 4) is the same as "while i ≤ 4."
• REPEAT n TIMES runs exactly n times; there's no loop variable you can read. If you need a counter, declare and increment one yourself.
• Infinite loop detection: find the variables in the stopping condition, then check whether the body ever changes them in the direction that would make the condition true. If the condition is i > 10 and the body does i ← i - 1, it never stops (assuming i starts ≤ 10).
• The final value of a loop variable after the loop is the value that made the condition true — one step past the last iteration's value. If the body ran with i = 1, 2, 3, 4, then i is 5 afterward.
• The exam's block-based pseudocode draws REPEAT UNTIL as a shape with the condition on top. Same semantics.
• Combining a loop with an accumulator (sum ← sum + i) is how sums, counts, and products are computed. The accumulator must be initialized before the loop.

Mistakes that cost points

• Running the body while the condition is true. REPEAT UNTIL is the opposite — body runs while false. This one flip is responsible for a large share of wrong loop answers.
• Forgetting the zero-iteration case. If the stopping condition is true before the loop starts, nothing inside runs. Check the initial state first.
• Reporting the last iteration's value instead of the final value. The variable's final value is the one that stopped the loop, which is one step beyond.
• Not initializing the accumulator. A sum that's never set to 0 before the loop is undefined. On the exam it's a logic error to spot.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

count ← 10
REPEAT UNTIL (count < 4)
{
    DISPLAY("hi")
    count ← count - 2
}

total ← 0
REPEAT 3 TIMES
{
    total ← total + 5
    total ← total * 2
}