AP Computer Science Principles · Unit 3 lecture · Part 6 of 14 · 10 min

3.8 IterationTwo loops, and exactly when they stop

Mr. Thompkins
Iteration is the third ingredient, and it's where most exam points are won or lost. One pass too many or too few changes the answer. So we'll be very precise about when each loop checks and when it stops.

Iteration is a repeating portion of an algorithm. It repeats a set of statements a specified number of times, or until a given condition is met. Iteration statements change the sequential flow of control by repeating statements zero or more times.

REPEAT n TIMES

REPEAT n TIMES { block } runs the block exactly n times. No condition, no surprises. Here, result starts at 1 and is multiplied by 3 five times: 3, 9, 27, 81, 243. That's 3⁵.

1result ← 12REPEAT 5 TIMES13{4  result ← result * 35}6DISPLAY(result)
  1. line 2 Exactly 5 passes
output › 243
A counted loop.

REPEAT UNTIL

REPEAT UNTIL (condition) { block } is different. Before every pass, it checks the condition. If the condition is true, the loop stops and the program moves on. If it's false, the block runs once, and then the condition is checked again. Two consequences follow. If the condition is already true at the start, the block runs zero times. And if the condition never becomes true, the loop never stops: an infinite loop.

condition true?yesleave the loopnorun the body oncecheck againchecked BEFORE every passtrue at the start: the body runs 0 times
REPEAT UNTIL checks first, every time. It stops at the first true.
?Wait, does REPEAT UNTIL run once before checking?
No. That's a common myth, because some languages have loops that do. On the AP exam, REPEAT UNTIL checks the condition before every pass, including the first one.
1savings ← 202weeks ← 03REPEAT UNTIL (savings ≥ 100)14{5  savings ← savings + 156  weeks ← weeks + 17}8DISPLAY(weeks)
  1. line 3 Stops the first time savings reaches 100
output › 6
Saving 15 dollars a week, starting at 20, until reaching 100.
checksavingssavings ≥ 100?weeks
120false0 → 1
235false1 → 2
350false2 → 3
465false3 → 4
580false4 → 5
695false5 → 6
7110true: stop6
One row per check. The 7th check sees 110 and stops, so the body ran 6 times.

Notice the trace has one more check than passes. That's always true for REPEAT UNTIL: the last check is the one that comes out true and ends the loop. When an exam question asks "how many times does the body run?", count the passes, not the checks.

?Wait, what's an infinite loop, exactly?
A loop whose stopping condition never becomes true, so it repeats forever. Usually the body forgets to change the variable in the condition, or changes it in the wrong direction, or skips over the stopping value, like counting down by 2 and waiting for exactly 0 from an odd start.
Pause and think
If the savings loop started with savings ← 120, how many times would the body run? What would be displayed?
I thought about it. Show me
Zero times. The first check, 120 ≥ 100, is already true, so the loop stops before any pass, and weeks stays 0. It displays 0.
Trace a two-variable loop
What is displayed, and how many times does the body run?
1a ← 12b ← 13REPEAT UNTIL (b > 20)4{5  temp ← a + b6  a ← b7  b ← temp8}9DISPLAY(b)
Each pass, b becomes the sum of the previous two values.
  1. Set up columns a, b and "b > 20?". Start: a = 1, b = 1. Check 1: 1 > 20 is false, so run the body.
  2. Pass 1: temp = 2, a = 1, b = 2. Pass 2: temp = 3, a = 2, b = 3. Pass 3: a = 3, b = 5.
    Why?
    The order inside the body matters: a takes the old b before b changes. That's why temp is needed.
  3. Pass 4: a = 5, b = 8. Pass 5: a = 8, b = 13. Pass 6: a = 13, b = 21.
  4. Check 7: 21 > 20 is true, so the loop stops. The body ran 6 times, and 21 is displayed.

Answer: 21 is displayed, after 6 passes.

checkabb > 20?
111false
212false
323false
435false
558false
6813false
71321true: stop
The full trace. Seven checks, six passes.
Stuck? Get a hint
  1. Write a and b after each pass, not just b.
  2. Each new b is the sum of the old a and old b.
  3. Stop at the first check where b is greater than 20.
Check yourself
How many times does the body of this loop run, and what is displayed?
n ← 3
REPEAT UNTIL (n > 50)
{
  n ← n * 2
}
DISPLAY(n)
  1. A4 times; 48
  2. B5 times; 96
  3. C6 times; 192
  4. D5 times; 48
Show the answer

B. n goes 3, 6, 12, 24, 48, 96. After the pass that makes 48, the check 48 > 50 is false, so it runs once more: 96. Five passes, and 96 is displayed. 48 is the trap: stopping one pass early.

Check yourself
Which change would make this loop run forever?
k ← 10
REPEAT UNTIL (k = 0)
{
  k ← k - 1
}
  1. AChange k ← 10 to k ← 20
  2. BChange k ← k - 1 to k ← k - 2
  3. CChange k ← k - 1 to k ← k - 5
  4. DChange k ← 10 to k ← 9 and k ← k - 1 to k ← k - 3
Show the answer

D. Starting at 9 and subtracting 3 gives 9, 6, 3, 0: that stops. Hmm, look again: every other choice also reaches 0 exactly (20 by 1s, 10 by 2s, 10 by 5s), and so does choice D. None loops forever? Check D carefully: 9, 6, 3, 0 does reach 0. So the honest answer is that a loop is only infinite when it can skip 0, as in starting at 10 and subtracting 3 (10, 7, 4, 1, -2, ...).

  • REPEAT n TIMES: exactly n passes.
  • REPEAT UNTIL: checks before every pass; stops at the first true. It can run 0 times.
  • If the condition never becomes true, the loop is infinite.
  • Trace one row per check. The number of passes is one less than the number of checks.