Skip to content

Tracing Loops

Learning Objectives

At the end of this sub-unit, students should

  • be able to trace the execution of a loop.
  • be able to use trace table.

Inadequacy of Pure Memory Model

We managed to trace the execution of code up to selection using our memory model. We did this by writing the states as comment. However, this will not be sufficient for reasoning about loops. In the case of if-statement, each line is executed at most once. Unfortunately, in the case of loop, the same line can be executed multiple times. So a static comment cannot fully capture this behavior.

Memory Model

One way to remedy this is to write the line that is being executed without regards for the actual structure. We can illustrate this approach by tracing the factorial for n = 3.

First, recap out solution for the factorial.

Factorial

1
2
3
4
5
6
7
# Assume n is initialized
res = n
val = n - 1
while val > 0:
  res = res * val
  val = val - 1
print(res)

The trace with memory model we had was the following.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# { n ↦ 3 }
res = n
# { n ↦ 3 , res ↦ 3 }
val = n - 1
# { n ↦ 3 , res ↦ 3 , val ↦ 2 }
while val > 0:    # ⇝  2 > 0  ⇝  True
                  #   ⇒ next line is Line 4
# { n ↦ 3 , res ↦ 3 , val ↦ 2 }
res = res * val   # ⇝  3 * 2  ⇝  6
# { n ↦ 3 , res ↦ 6 , val ↦ 2 }
val = val - 1     # ⇝  2 - 1  ⇝  1
# { n ↦ 3 , res ↦ 6 , val ↦ 1 }
while val > 0:    # ⇝  1 > 0  ⇝  True
                  #   ⇒ next line is Line 4
# { n ↦ 3 , res ↦ 6 , val ↦ 1 }
res = res * val   # ⇝  6 * 1  ⇝  6
# { n ↦ 3 , res ↦ 6 , val ↦ 1 }
val = val - 1     # ⇝  1 - 1  ⇝  0
# { n ↦ 3 , res ↦ 6 , val ↦ 0 }
while val > 0:    # ⇝  0 > 0  ⇝  False
                  #   ⇒ next line is Line 6
# { n ↦ 3 , res ↦ 6 , val ↦ 0 }
print(res)        # ⇝  print(6)

1
6

This can be quite tedious, but this is the most explicit way to trace. Often, it is good to do this at least once or twice. But hopefully, you can do this entirely in your mind in the future. What we will explore next is how we can simplify this by stripping the code and keeping only the essence of the state.

Trace Table

To make a trace table, we keep the code aside and we look only at the state. Using the factorial of 3 above as an example, we want a nicer way to visualize the following.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# { n ↦ 3 }
# { n ↦ 3 , res ↦ 3 }
# { n ↦ 3 , res ↦ 3 , val ↦ 2 }  -- before loop
# { n ↦ 3 , res ↦ 3 , val ↦ 2 }
# { n ↦ 3 , res ↦ 6 , val ↦ 2 }
# { n ↦ 3 , res ↦ 6 , val ↦ 1 }  -- end of iteration #1
# { n ↦ 3 , res ↦ 6 , val ↦ 1 } 
# { n ↦ 3 , res ↦ 6 , val ↦ 1 }
# { n ↦ 3 , res ↦ 6 , val ↦ 0 }  -- end of iteration #2
# { n ↦ 3 , res ↦ 6 , val ↦ 0 }  -- after loop

Looking at the way we arrange the state above, we can represent this as a table such that.

  • Each row represents the state at the start / during / at the end of the iteration.
    • We may have two special rows corresponding to before (pre) and after (post) the loop.
  • Each column represents the values of a variable over the entire execution.
    • We may use line number as a subscript to represent the variable after a particular line.
      • This is especially useful for a variable that is modified multiple times within the loop-body.
    • We may omit a variable if the value is irrelevant.
    • If we wish to ignore a value, we can leave the cell blank.

This gives us the following visualization. Note that res3 and val3 basically corresponds to the value of these variable at the beginning of the loop. On the other hand, res5 and val5 corresponds to the value of these variable at the end of the loop.

Iteration n res3 val3 res5 val5
pre 3 3 2
1 3 3 2 6 1
2 3 6 1 6 0
post 3 6 0

The answer is then the value of res5 on the last row. To see that this is indeed the case --and to showcase the benefit of trace table-- we can show the trace for n = 5.

Iteration n res3 val3 res5 val5
pre 5 5 4
1 5 5 4 20 3
2 5 20 3 60 2
3 5 60 2 120 1
4 5 120 1 120 10
post 5 120 10

We can even use trace table for while-loop with an arbitrary repetition such as the Collatz conjecture. The code for the Collatz conjecture is reproduced below.

Collatz Conjecture

1
2
3
4
5
6
7
8
9
# Assume n is initialized
step = 0           # count the step
while n > 1:       # alternatively, while n != 0:
  step = step + 1  # take one step
  if n % 2 == 0:   # n is even
    n = n // 2     #   use // to keep n as integer
  else:            # n is odd
    n = 3 * n + 1  #   3n + 1
print(step)

And trace starting with n = 5 is shown below.

Iteration n3 step3 n % 2 == 0 step4 n6 n8
pre 5 0
1 5 0 False 1 16
2 16 1 True 2 8
3 8 2 True 3 4
4 4 3 True 4 2
5 2 4 True 5 1
post 1 5

Here, we say that step3 holds the answer because it is the last value of step before we exit the loop.