Lesson 3.8

Trace a loop: iterations and final values

Part 3: RepetitionReading, about 6 min2 exercises in this lesson, in Python1 exercise in this lesson, in Java

Tracing a loop

By the end of this you will be able to trace a loop with a table, say how many times its body runs, give the values the variables hold when it stops, and count the turns of a nested loop without tracing every one.

Like the lesson on tracing branches, this lesson has no new code. It is about reading a loop the way a trace question asks you to.

A trace table for a loop

Keep one column for each variable and one for the output. Go through the program line by line, and add a row each time a line changes a variable or prints something. Each change gets its own row, even when two variables change on the same turn.

A reading club doubles the pages it reads each week, starting at 5, until it reads 40 or more.

pages = 5
weeks = 0
while pages < 40:
    pages = pages * 2
    weeks = weeks + 1
print(weeks)
print(pages)

public static void main(String[] args) {
    int pages = 5;
    int weeks = 0;
    while (pages < 40) {
        pages = pages * 2;
        weeks = weeks + 1;
    }
    System.out.println(weeks);
    System.out.println(pages);
}

`pages`	`weeks`	output
5
	0
10
	1
20
	2
40
	3
		3
		40

Before each turn, check the condition with the values the variables hold right now. With pages at 5, 10 and 20, pages < 40 is true, so the body runs. With pages at 40, it is false, because 40 is not less than 40. The loop stops and the program moves on to the lines after it.

How many times the body runs

Count the turns, not the values. Here the body ran 3 times: once for each time weeks went up by 1, to 1, 2 and 3. The 0 was set before the loop. The condition was checked 4 times, because the last check is the one that comes out false and ends the loop. A loop whose condition is checked n times runs its body n - 1 times.

If the condition is false at the very first check, the body runs 0 times. Start pages at 50 and nothing in the loop runs: the program prints 0, then 50.

The final values

When a while loop stops, each variable holds the value it had at the last check, the one that came out false. So the final value is never one that makes the condition true.

The final value does not have to land exactly on the number in the condition. Start pages at 3 instead:

Turn	`pages` at the end of the turn	`weeks` at the end of the turn
1	6	1
2	12	2
3	24	3
4	48	4

The loop runs a fourth time because 24 is still less than 40. That turn takes pages past 40, to 48. The program prints 4, then 48. A common mistake is to stop the trace at 24 because the next value "goes too far". The loop cannot know that until it has run the turn.

A for loop's turns

A for loop counts for you, so you can often find its number of turns without a trace. From the lessons on for loops: when the end b is bigger than the start a, range(a, b) in Python, or a Java counter that starts at a and keeps going while it is < b, runs b - a turns. With <= b in Java, or range(a, b + 1) in Python, it runs one more turn: b - a + 1.

After the loop, the counter itself is different in the two languages. In Python, a for counter keeps the last value it was given, so after for i in range(4) it holds 3, not 4. In Java, a counter made in the for line exists only inside the loop, so a line after the loop cannot use it.

Counting the turns of a nested loop

When the inner loop always takes the same number of turns, multiply, as in the lesson on nested loops: 3 outer turns of 5 inner turns each is 15.

When the inner loop's start or end uses the outer counter, the inner loop takes a different number of turns on each outer turn. Then count each outer turn on its own, and add them up.

Four players each play every other player once. This program counts the games.

games = 0
for a in range(4):
    for b in range(a + 1, 4):
        games = games + 1
print(games)

public static void main(String[] args) {
    int games = 0;
    for (int a = 0; a < 4; a++) {
        for (int b = a + 1; b < 4; b++) {
            games = games + 1;
        }
    }
    System.out.println(games);
}

`a`	`b` takes	Inner turns
0	1, 2, 3	3
1	2, 3	2
2	3	1
3	none	0

The inner loop starts at a + 1, so it starts again on every outer turn, one place further along. When a is 3, it would start at 4, which is already at the end, so it runs 0 times. In total the body runs 3 + 2 + 1 + 0 = 6 times, so the program prints 6. Multiplying 4 by 4 would give 16, which is wrong here, because the inner loop does not take 4 turns each time.

The trace questions below show their code in Python or in Java. Apart from what happens to a for counter after the loop, every rule on this page works the same way in Python and Java.

Now try it yourself on the questions below.

Exercise 3.8.1 · Trace itTrace: digit sum

Complete the trace table for this Python code. In Python, // divides and keeps only the whole number part, and % gives the remainder. [3]

Line 1: n = 4721n = 472
Line 2: total = 02total = 0
Line 3: while n > 0:3while n > 0:
Line 4, indented 1 level: digit = n % 104    digit = n % 10
Line 5, indented 1 level: total = total + digit5    total = total + digit
Line 6, indented 1 level: n = n // 106    n = n // 10
Line 7: print(total)7print(total)

Fill in one row each time a line changes n, digit or total, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Row	n	digit	total	output
1
2
3
4
5
6
7
8
9
10
11
12

Exercise 3.8.2 · Trace itTrace: nested count

Complete the trace table for this Python code. range(a, b) gives the whole numbers from a up to, but not including, b, and range(i) starts at 0. [3]

Line 1: count = 01count = 0
Line 2: for i in range(1, 3):2for i in range(1, 3):
Line 3, indented 1 level: for j in range(i):3    for j in range(i):
Line 4, indented 2 levels: count = count + 14        count = count + 1
Line 5: print(count)5print(count)

Fill in one row each time a line changes i, j or count, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Row	i	j	count	output
1
2
3
4
5
6
7
8
9
10

Exercise 3.8.1 · Trace itTrace: step loop

Complete the trace table for this Java code. Then answer the question below the table. [3]

Line 1: int i = 10;1int i = 10;
Line 2: int steps = 0;2int steps = 0;
Line 3: while (i > 0) {3while (i > 0) {
Line 4, indented 1 level: i = i - 3;4    i = i - 3;
Line 5, indented 1 level: steps = steps + 1;5    steps = steps + 1;
Line 6: }6}
Line 7: System.out.println(i);7System.out.println(i);

Fill in one row each time a line changes i or steps, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Row	i	steps	output
1
2
3
4
5
6
7
8
9
10
11

How many times does the loop body run?