Skip to content
Topos Uranos
English

Loops

Summary

The lesson From the problem to the algorithm recognized three ways of composing steps: sequence, decision and repetition. The first two already have their notation in C++; this lesson gives the third its own. It studies the three forms of the loop: while, which evaluates its condition before each iteration and may never execute its body; do, which evaluates it afterward and executes the body at least once; and for, which gathers in one line the initialization, the condition and the update of the variable that governs the repetition. It shows that the three express one and the same mechanism, so that each can be transformed into the others, and it teaches how to choose the clearest; it presents break and continue, which alter the course of an iteration; and it ends with nested loops, whose inner body is executed a number of times that is computed with a sum. The instrument that accompanies the whole lesson is the trace table: tracing a loop by hand, iteration by iteration, is the way to predict how many times its body is executed and what it leaves behind when it exits.

Learning objectives

  1. Write a while, do or for loop for a given repetition, choosing the clearest form.
  2. Trace a loop by hand with its trace table and predict how many times the body is executed.
  3. Transform a loop from one form into another while preserving its meaning.
  4. Write nested loops and compute how many times the inner body is executed.

while

The form of a while

A while is written like this:

C++ code
while (condition) {    body}

Its meaning is stated in three steps: the condition is evaluated; if it is false, the loop ends and execution continues after the brace that closes it; if it is true, the body is executed and execution returns to the first step. Each execution of the body is called an iteration (or pass). The condition is a Boolean expression like those of the lesson Relations and logic, and the body is a block; the rule of braces that the lesson Decisions established also applies here: the body of a loop always has braces, even when it contains a single statement.

Two consequences follow from the definition. The first: the condition is evaluated before each iteration, so that if it is false from the start, the body is not executed even once. The second: for the loop to end, the body must change something that the condition reads; if nothing changes, a condition that was true once will be true forever. Now, changing is not enough: the lesson From the problem to the algorithm showed that what is needed is a natural quantity that decreases on every iteration, the variant, and the lesson Designing correct loops will turn it into a method.

Division by repeated subtraction

The course’s first algorithm with repetition was division by repeated subtraction: as long as the remainder is at least the divisor, the divisor is subtracted from it and one is added to the quotient. Written in C++, the algorithm carries over almost word for word.

ExampleThe quotient and the remainder by subtraction
C++ program
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
Program input
23 7
Output
23 = 7 · 3 + 2

Lines 9 and 10 give the variables their initial value: nothing has been subtracted yet, so the quotient is 0 and the remainder is the whole dividend. Line 11 is the condition of step 2 of the algorithm; lines 12 and 13, the body. The program assumes, like the algorithm, that a≥0a \geq 0 and b>0b > 0: with b=0b = 0, line 12 would not change r and the loop would not end.

The trace table

Tracing the loop by hand means filling in a table: one row per iteration, one column per variable and one for the condition, evaluated at the start of the iteration. Row 0 records the state before the first evaluation; the last row, the evaluation that turns out false and ends the loop.

ExampleThe trace of 23 divided by 7

Proof

  1. Before the loop, lines 9 and 10 are executed: q=0q = 0 and r=23r = 23. This is row 0; the condition has not been evaluated yet.

  2. First iteration. The condition 23≥723 \geq 7 is true, so the body is executed: rr becomes 16 and qq becomes 1. Then execution returns to line 11.

  3. Second iteration. 16≥716 \geq 7 is true: rr becomes 9 and qq becomes 2.

  4. Third iteration. 9≥79 \geq 7 is true: rr becomes 2 and qq becomes 3.

  5. The fourth evaluation, 2≥72 \geq 7, is false: the body is not executed, the loop ends and line 15 writes 23=7⋅3+223 = 7 \cdot 3 + 2.

The trace teaches how to count. The body was executed three times, as many as the quotient, and the condition was evaluated four: one per iteration and one more, the one that fails. This relation holds for every while that ends through its condition: if the body is executed kk times, the condition is evaluated k+1k + 1 times. And the extreme case confirms it: with the input 5 7, the first evaluation, 5≥75 \geq 7, is already false, the body is executed zero times, and the program writes 5=7⋅0+55 = 7 \cdot 0 + 5, which is correct. A well-written while handles, with no additional code, the case in which there is nothing to repeat.