Loops

The course’s shared problem was finding the average and the maximum of a sequence of measurements. Until now, this has been done with built-in functions. This lesson defines the structure that does the same work step by step: the loop.

A loop makes a block of code execute more than once. How many times it executes is either known in advance or depends on a condition; this distinction determines the types of loops.

Iterating Over a Collection

The most commonly used form is advancing through a collection’s elements in order:

measurements = [12, 18, 7, 25, 14]

for measurement in measurements:
    print(measurement)
# 12 / 18 / 7 / 25 / 14   (each on its own line)

The loop variable (measurement) is bound to the next element on every iteration. As many iterations run as there are elements; there is no need to keep a counter, query the length, or check a bound.

This form’s advantage is that it makes off-by-one errors impossible. In loops with a manually managed counter, the most common error is processing one element too few or too many; iterating directly over the collection eliminates this class of error.

The Counted Loop

Some problems need not the element itself but its position: processing the first three measurements, walking two arrays at once, or repeating a fixed number of times.

for i in range(5):
    print(i, end=" ")
print()                      # 0 1 2 3 4

for i in range(len(measurements)):
    print(f"measurement {i}: {measurements[i]}")
# measurement 0: 12 ... measurement 4: 14

Counting starting from zero and leaving the upper bound excluded is a common convention: range(5) produces five values, and the last one is $4$. The benefit of this arrangement is that range(len(array)) gives exactly the valid indices.

If only the position number is needed, a counted loop is the right tool. If both the position and the element are needed, most languages offer a construct that provides both together; looking the element up by index again is unnecessary work.

The Conditional Loop

When the number of iterations is not known in advance, a conditional loop is used. The condition is tested before every iteration; when it no longer holds, the loop ends.

remaining = 100
round_count = 0

while remaining > 1:
    remaining = remaining // 2   # halves on every iteration
    round_count += 1

print(round_count)           # 6

This loop finds how many times a number can be halved. The number of iterations is not known at the start; it depends on the initial value. The same calculation is also the source of the cost in the binary search example from the previous course.

One variant of the conditional loop tests the condition at the end of the iteration, so the body runs at least once. The pattern of asking the user until a valid value is obtained requires this form.

The Termination Guarantee

Nothing guarantees that a loop will stop; the person writing the program must ensure it. The rule is: on every iteration, there must be a change that moves toward making the condition false.

In the example above, remaining shrinks on every iteration and heads toward zero; values between zero and one make the condition false. This decreasing quantity is the loop’s justification for termination.

If no such justification can be established, the loop can run forever:

remaining = 100
while remaining > 1:
    remaining = remaining // 2
    if remaining == 3:
        remaining = 100      # jump backward: the decrease guarantee is broken

This loop never ends. The program stays running, keeps the processor busy, and does not terminate unless stopped from outside. Because an infinite loop produces no runtime error, it falls into the logic error class defined in the first lesson.

Deliberate infinite loops also exist: a server, while waiting for requests, does not intentionally stop. In that case, exit comes not from the loop condition but from the break statements covered in the next lesson, or from an external signal.

The Accumulator Pattern

The most common use of loops is accumulating a value across iterations. The pattern consists of three steps: initialize the accumulator, update it on every iteration, use it after the loop.

measurements = [12, 18, 7, 25, 14]

total = 0                        # 1. initial value
for measurement in measurements:
    total += measurement         # 2. update on every iteration

average = total / len(measurements)   # 3. use the result
print(total, average)            # 76 15.2

The choice of initial value is the operation’s identity element: zero for addition, one for multiplication. An incorrectly chosen initial value silently produces a wrong result.

Finding the maximum value follows the same pattern, but the initial value requires more care:

largest = measurements[0]        # the first element is taken as the starting point
for measurement in measurements:
    if measurement > largest:
        largest = measurement

print(largest)                   # 25

Starting from zero here would be wrong: if all the measurements were negative, the result would incorrectly come out as zero. The correct starting point is the array’s first element — and this assumes the array is not empty. An empty input is the standard edge case for this kind of code and must be handled before the loop.

The course’s shared problem has thus been solved without built-in functions: two loops, two accumulators.

The Loop Invariant

Termination is only one of two questions about a loop; the second is correctness — why is the result correct once it ends?

The answer is given by the concept of the loop invariant: a statement that remains true at the start and end of every iteration. The invariant of the accumulator loop is this — total is the sum of the elements visited so far.

The invariant is tested in three places. It is true before entering the loop (no element has been visited, the total is zero). Every iteration preserves it (one element is visited, that same element is added to the total). Once the loop ends, every element has been visited; the invariant then states that total is the sum of all the elements. That is the desired result.

These three steps prove the loop’s correctness without tracing individual iterations. The invariant of the loop that finds the maximum is written the same way: largest is the maximum of the elements visited so far. Writing this statement also explains why the initial value must be the first element — if it started at zero, the invariant would already be false before entering the loop.

The habit of writing invariants is the foundation of correctness proofs for algorithms, and it is formalized in the Algorithms course.

Nested Loops

A loop’s body can contain another loop. Every iteration of the outer loop runs the inner loop in full; the total number of iterations is the product of the two.

for i in range(3):
    for j in range(2):
        print(i, j, end="  ")
print()
# 0 0  0 1  1 0  1 1  2 0  2 1

Multiplicative growth is the main cost of nested loops: every new level multiplies the amount of work. This observation is the starting point of the concept of algorithmic complexity and is formalized in the Algorithms course. The intuition sufficient for this course is this: as data grows, the cost of nested loops grows far faster than that of single-level loops.

Summary

• Iterating over a collection processes elements in order and eliminates off-by-one errors.
• A counted loop is used when the element’s position, not the element itself, is needed (counting starts at zero, the upper bound is excluded); a conditional loop is used when the number of iterations is not known in advance.
• A loop’s termination is guaranteed by a change on every iteration that moves toward making the condition false; without such a change, the loop runs forever.
• The accumulator pattern has three steps: initialize, update on every iteration, use afterward; the initial value is the operation’s identity element, and it is the first element when searching for a maximum.
• The loop invariant is a statement that stays true on every iteration, and it justifies a loop’s correctness without tracing individual iterations.
• In nested loops, the total number of iterations grows multiplicatively.

Next Step

Loops flow from start to end, but sometimes a decision must be made partway through an iteration: exiting early once the target is found, or skipping an invalid element and continuing. The next lesson covers the statements that redirect loop flow from the inside, and their effect on readability.