Repetition

When giving directions, we naturally speak in repetitions: "walk 50 steps then turn right", or "walk till the next crossing, then take a right turn". Other everyday examples of the same pattern:

• clap your hands five times
• walk 10 steps ahead
• jump on the spot till you get tired

Each of these asks for something to be done repeatedly — either a given number of times, or until some condition is met. In the card game of Example 4.7, likewise, if 10 cards are to be drawn, the scoring pseudocode must be repeated 10 times before the winner can be decided.

Iteration and loops

In programming, repetition is also called iteration or a loop. A loop in an algorithm means the execution of some program statements repeatedly, till some specified condition is satisfied.

Example 4.8 — average of 5 numbers (known repetition count)

Task: accept 5 numbers and find their average.

Step 1: Set count = 0, sum = 0
Step 2: While count < 5, repeat steps 3 to 5
Step 3:     Input a number to num
Step 4:     sum = sum + num
Step 5:     count = count + 1
Step 6: Compute average = sum/5
Step 7: Print average

Here a counter named count keeps track of how many times the loop has run. After every iteration, count is incremented by 1, and the loop continues until it has performed the set number of repetitions given in the iteration condition (count < 5). The flowchart (Figure 4.10) shows the loop as an arrow that leads back up into the decision diamond; when the condition finally fails, control exits to compute and print the average.

Example 4.9 — average of numbers until 0 is entered (unknown repetition count)

Sometimes we do not know beforehand how many times a set of statements must repeat. Such unknown-count repetition is handled with the WHILE construct: keep checking a condition, and repeat as long as it holds.

Task: accept numbers until the user enters 0, then find their average.

Step 1: Set count = 0, sum = 0
Step 2: Input num
Step 3: While num is not equal to 0, repeat Steps 4 to 6
Step 4:     sum = sum + num
Step 5:     count = count + 1
Step 6:     Input num
Step 7: Compute average = sum/count
Step 8: Print average

We have no idea how many numbers the user will type before entering 0; the algorithm simply re-checks the condition after every number, and stops the moment the condition becomes false. Figure 4.11 shows the flowchart. Two details deserve attention:

• num is read twice — once before the loop (so the very first check has a value to test) and once at the end of each iteration (so the next check tests the newest value). Without the first read, the loop condition would be tested on nothing; without the second, the loop would test the same number forever.
• The average divides by count, not by a fixed 5 — because the quantity of numbers entered is only known at the end, count (the number of values actually summed) is the right divisor. The terminating 0 itself is never added and never counted.

Contrast between the two examples

• Example 4.8: the repetition count is fixed in advance (exactly 5), so a counter drives the loop. …