3.8 IterationTwo loops, and exactly when they stop

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)
- line 2 Exactly 5 passes
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.
?Wait, does REPEAT UNTIL run once before checking?
1savings ← 202weeks ← 03REPEAT UNTIL (savings ≥ 100)14{5 savings ← savings + 156 weeks ← weeks + 17}8DISPLAY(weeks)
- line 3 Stops the first time savings reaches 100
| check | savings | savings ≥ 100? | weeks |
|---|---|---|---|
| 1 | 20 | false | 0 → 1 |
| 2 | 35 | false | 1 → 2 |
| 3 | 50 | false | 2 → 3 |
| 4 | 65 | false | 3 → 4 |
| 5 | 80 | false | 4 → 5 |
| 6 | 95 | false | 5 → 6 |
| 7 | 110 | true: stop | 6 |
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?
I thought about it. Show me
1a ← 12b ← 13REPEAT UNTIL (b > 20)4{5 temp ← a + b6 a ← b7 b ← temp8}9DISPLAY(b)
- Set up columns a, b and "b > 20?". Start: a = 1, b = 1. Check 1: 1 > 20 is false, so run the body.
- 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. - Pass 4: a = 5, b = 8. Pass 5: a = 8, b = 13. Pass 6: a = 13, b = 21.
- 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.
| check | a | b | b > 20? |
|---|---|---|---|
| 1 | 1 | 1 | false |
| 2 | 1 | 2 | false |
| 3 | 2 | 3 | false |
| 4 | 3 | 5 | false |
| 5 | 5 | 8 | false |
| 6 | 8 | 13 | false |
| 7 | 13 | 21 | true: stop |
Stuck? Get a hint
- Write a and b after each pass, not just b.
- Each new b is the sum of the old a and old b.
- Stop at the first check where b is greater than 20.
n ← 3
REPEAT UNTIL (n > 50)
{
n ← n * 2
}
DISPLAY(n)- A4 times; 48
- B5 times; 96
- C6 times; 192
- 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.
k ← 10
REPEAT UNTIL (k = 0)
{
k ← k - 1
}- AChange k ← 10 to k ← 20
- BChange k ← k - 1 to k ← k - 2
- CChange k ← k - 1 to k ← k - 5
- 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.