C / LOOPS AND JUMPS
Tracing a loop by hand before trusting it
Trace a C loop by hand with a trace table, predict its exit state, then confirm that prediction with temporary printf output instead of guessing.
What you will learn
- Build a trace table: one column per loop variable, one for the guard's truth value.
- Record every row at the same instant, just before the condition is evaluated.
- Write the failing row too; it holds the values the code after the loop will read.
- Reprint your table with printf and diff your prediction against the real run.
Understanding Tracing a loop by hand before trusting it
A hand trace is a table, and the discipline is in choosing what a row means. Pick one instant in the cycle, normally the moment just before the condition is evaluated, and give the table a column for every variable the loop reads or writes plus a column for the condition's value at that instant. Each row is then a photograph of the loop's whole state at the same point in successive passes, so comparing two adjacent rows tells you exactly what one pass changed. If some rows are taken at the top and others after the update, the table stops being comparable and you will read a difference the code never produced.
The row worth the most is the last one, where the condition is false. That row is the only place the post-loop value of the counter appears, and the number of rows above it is the iteration count, so questions like whether the body ran for the last element, or what the code below the loop sees, are answered by looking there instead of re-reading the header. Side effects decide where a row's numbers come from: if the condition itself contains i++ or a compound assignment, the variable has already changed before the body starts, and the table has to say which side of that change it is showing.
Tracing is worth nothing if you trace your intent instead of the operators, so evaluate what is written: integer division truncates, /= stores the result back, and a signed value compared against an unsigned one is converted first. The check is mechanical. Put a printf inside the body that prints exactly your table's columns, shrink the input until five or six rows cover the whole run, and compare line by line; the first row that disagrees is the payoff, because either your model of an operator is wrong or the loop is wrong, and neither would have surfaced by staring at the code again.
<stdio.h>
int main(void)
{
int n = 1024;
int sum = 0;
int iter = 0;
printf("iter | n | n%%10 | sum\n");
while (n != 0) {
iter++;
printf("%4d | %5d | %4d | %3d", iter, n, n % 10, sum);
sum += n % 10;
n /= 10;
printf(" -> n=%d sum=%d\n", n, sum);
}
printf("exit | %5d | | %3d (n != 0 is now false)\n", n, sum);
return 0;
}
A loop is a handful of variables observed at one repeated instant, so tracing it means writing that state down row by row, including the row where the condition finally fails.
Worked examples
Where the increment lands
The traced rows show what the body saw, while the row after the loop shows the value the increment left behind.
<stdio.h>
int main(void)
{
int a[5] = {3, 7, 2, 9, 4};
int best = 0;
int i;
for (i = 1; i < 5; i++) {
printf("top of body: i=%d a[i]=%d best=%d a[best]=%d\n",
i, a[i], best, a[best]);
if (a[i] > a[best])
best = i;
}
printf("after loop: i=%d best=%d a[best]=%d\n", i, best, a[best]);
return 0;
}
Example explained
Line 1int i is declared above the header on purpose: a trace has to read i after the loop, and a variable declared inside the header stops existing at the closing brace.
Line 2The printf at the top of the body is one table row, so each line shows the state the comparison a[i] > a[best] actually worked with.
Line 3No row prints i = 5, because the test that sees 5 fails and the body is skipped; the last body row is therefore i = 4.
Line 4The final line is the failing row: i = 5 is what any later code would find, and best = 3 is the result the loop was computing.
A side effect hidden in the condition
When the update lives inside the test, the body sees a counter that has already moved on, so the table needs to name which side of the side effect it records.
<stdio.h>
int main(void)
{
const char *s = "abc";
int i = 0;
char c;
while ((c = s[i++]) != '\0') {
printf("body: c=%c i is already %d\n", c, i);
}
printf("exit: c=%d i=%d\n", c, i);
return 0;
}
Example explained
Line 1(c = s[i++]) reads s[i] and then bumps i, so the increment is finished before the body ever starts.
Line 2The first body row pairs c = 'a', which came from index 0, with i = 1, which is why one plain i column would be ambiguous here.
Line 3The exit line runs after the test that stored the terminator in c and pushed i to 4, so i ends one past the terminator rather than at the string length.
Line 4Printing c with %d shows 0 because the terminating character is the value zero, and char is promoted to int for the variadic call.
Important notes
A trace only proves behaviour for the values traced, so choose awkward inputs: an input that makes the guard false immediately, one that gives a single pass, and the largest the guard allows.
stdout is block buffered when redirected to a file or pipe, so trace lines from a loop that crashes can be lost; use fprintf(stderr, ...) or fflush(stdout) when tracing a loop that faults.
Common mistakes
Recording each row after the update instead of before the test: the whole table shifts by one, every internal row still looks plausible, and the predicted final value is wrong.
Ending the table at the last successful iteration, so the counter's post-loop value is never written down and the code below the loop gets reasoned about with the wrong number.
Tracing the intended arithmetic rather than the written operators, such as reading n /= 2 as if n kept its old value or forgetting that 7 / 2 is 3, which makes the table agree with the plan and hides the bug.
Try it yourself
Change, predict, then run
Type int i = 0, s = 0; while (i < 5) { s += i * i; i++; } into an editor and write the complete table by hand, one row per test including the test that fails. Then add one printf at the top of the body and one after the loop, run it, and find the first row where your prediction and the run disagree.
Open the C workspaceCheck your understanding
You trace for (i = 0; i < 3; i++) with one row per condition test, each row recorded just before the test. How many rows does a complete table have, and what is in the last one?
- Three rows, the last with i = 2 and the condition true.
- Four rows, the last with i = 4, since the increment runs once more after the test fails.
- Four rows, the last with i = 3 and the condition false.
- Three rows, plus a note that i ends at 3; the failing test is not part of the trace.
Show answer
The condition is tested one more time than the body runs, so three body executions mean four tests and four rows, and the last row records i = 3 with the guard false. That row is where the post-loop value of i comes from. Option 0 is tempting because it matches the number of body runs, but it stops at the last successful pass and never writes down the value later code will read; option 1 is wrong because a failed test transfers control out of the loop without executing the increment again.