Aim for FiveComputer Science Principles

Unit 3 · Topic 3.8

3.8 Iteration

Iteration means repeating steps. This topic covers the exam's two loops, REPEAT n TIMES and REPEAT UNTIL, how to count how many times a loop runs, and how loops can run zero times or never stop.

Key terms

  • iteration
  • loop
  • REPEAT n TIMES
  • REPEAT UNTIL
  • infinite loop

Why loops

Iteration is a part of an algorithm that repeats, either a set number of times or until a condition is met. "Stir 20 times" and "keep stirring until the sauce is thick" are both iteration.

Loops change the sequential flow of control by sending the program back to run a block again. A loop body can run zero or more times.

REPEAT n TIMES

This loop runs its block exactly n times.

total ← 0 REPEAT 4 TIMES { total ← total + 5 } DISPLAY(total)

The block runs 4 times, adding 5 each time, so it displays 20.

REPEAT UNTIL

This loop keeps running its block until the condition becomes true. The condition is checked before each pass, including the very first one:

x ← 1 count ← 0 REPEAT UNTIL (x > 20) { x ← x * 3 count ← count + 1 } DISPLAY(x) DISPLAY(count)

x goes 1, 3, 9, 27. After x becomes 27, the check 27 > 20 is true, so the loop stops. It displays 27 3: the final x, then the number of passes.

Notice the condition says when to stop, not when to keep going. The loop continues while the condition is false.

Zero passes and infinite loops

Because the condition is checked first, a REPEAT UNTIL loop whose condition is already true never runs its body at all. If n starts at 10, REPEAT UNTIL (n ≥ 5) skips straight past the loop.

An infinite loop happens when the stopping condition can never become true. In this segment, k goes 1, 3, 5, 7, 9, 11, ... and skips right over 10, so k = 10 is never true and the loop never ends:

k ← 1 REPEAT UNTIL (k = 10) { k ← k + 2 }

Using k ≥ 10 instead would stop it after k reaches 11. Checking with ≥ or ≤ rather than = is a common way to make a loop safer.

Counting passes

To count how many times a loop runs, trace it in a table with one row per pass. Write the values at the moment the condition is checked, then what changes during the pass. Don't count the final check that stops the loop as a pass.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Count the passes

    What does this display?n ← 3 REPEAT UNTIL (n = 0) { DISPLAY(n) n ← n - 1 } DISPLAY("Go")

    Show the solution
    1. Step 1: Check: n = 3, is n = 0? No. Pass 1: display 3, n becomes 2.
    2. Step 2: Check: n = 2, not 0. Pass 2: display 2, n becomes 1.
    3. Step 3: Check: n = 1, not 0. Pass 3: display 1, n becomes 0.
    4. Step 4: Check: n = 0, so the condition is true and the loop stops. Then "Go" is displayed.
    5. Step 5: The body ran 3 times.

    Answer: 3 2 1 Go

  2. Example 2

    Does it ever run?

    What does this display?n ← 10 REPEAT UNTIL (n ≥ 5) { n ← n + 1 } DISPLAY(n)

    Show the solution
    1. Step 1: Before the first pass, the condition is checked: 10 ≥ 5 is true.
    2. Step 2: Since the condition is already true, the body never runs.
    3. Step 3: n is still 10.

    Answer: 10

Common mistakes

  • Reading REPEAT UNTIL as "repeat while." It stops when the condition becomes true.
  • Assuming a REPEAT UNTIL body always runs at least once. The check comes first, so it may run zero times.
  • Missing an infinite loop caused by a condition with = that the variable jumps past, or by a body that never changes the variable in the condition.
  • Counting the final check as an extra pass, giving an answer one too high.

On the exam

  • Expect to trace loops and say what's displayed or how many times the body runs. A pass-by-pass table is the safest method.
  • Written Response 2(a) may ask how the loop in your own procedure works, such as when it stops or how many times it runs. Know your loop's stopping condition and what changes each pass.

Connected topics

Videos

Check yourself

4 questions on 3.8 Iteration. Pick an answer to see if you got it, and why.

Question 1 of 4

What is displayed when the following code segment is run? x ← 1 REPEAT 4 TIMES { x ← x * 3 } DISPLAY(x)

Question 2 of 4

What is displayed when the following code segment is run? n ← 1 count ← 0 REPEAT UNTIL (n > 50) { n ← n * 2 count ← count + 1 } DISPLAY(count) DISPLAY(n)

Question 3 of 4

What is displayed when the following code segment is run? k ← 10 REPEAT UNTIL (k ≥ 10) { k ← k + 1 DISPLAY(k) } DISPLAY("done")

Question 4 of 4

Which code segment results in an infinite loop?

0 of 4 answered