Foundations · Iteration

Dry-run the loop before you trust it

Q: What are the three parts of a loop?

Initialisation, condition and step. sum = 0 and n = 4729 run once before anything else, n > 0 is tested before every pass, and n = n / 10 runs at the end of every pass. A for puts all three in one header and a while scatters them, but all three always exist — if you cannot point at the step line, you have an infinite loop.

Q: How many times does for (i = 0; i <= n; i++) run?

n + 1 times, not n . Write out the values i actually takes — 0, 1, 2 … n — and count them. With i < n the list stops at n - 1 and there are n of them, which is why < is the correct operator for walking an array of length n .

Q: What actually causes an infinite loop?

A condition that can never become false, which nearly always means the step is missing, moving the wrong way, or changing a different variable than the one being tested. Delete n = n / 10 from the digit-sum loop and n stays 4729 for ever. Find it on paper: name the variable in the condition, then find the line in the body that moves it toward false.

Q: What is the difference between break and continue?

break leaves the loop immediately — no step, no further condition check. continue skips the rest of the body and jumps straight to the next condition check. The trap is continue inside a while , where the step line usually sits at the bottom of the body: continue jumps over it and the loop hangs. In a for the step lives in the header, so it still runs.

Q: Dry-run this loop for me and show your table.

One column per variable plus a column for the condition, one row per pass, filled left to right in statement order. For 4729 the digit, sum and n columns read 9 / 9 / 472 , then 2 / 11 / 47 , then 7 / 18 / 4 , then 4 / 22 / 0 . Then write the row where n > 0 is false — that row is part of the answer and it is the one people leave out.

A loop is three decisions: where to start, when to stop, what changes each pass. Fill in a trace table by hand and all three become visible — along with every off-by-one and every loop that never ends.

Build the trace table for 4729, one cell at a time →

1 · Startsum = 0, n = 4729. Runs once, before the first pass.

→

2 · Checkn > 0 ? False and the loop is over. Tested before every pass.

→

3 · Bodydigit = n % 10, then sum = sum + digit. The actual work.

→

4 · Updaten = n / 10, then back to the check. Without this it never ends.

01 The idea

Three decisions, spread across time

A loop is how a program does the same thing many times without you typing it many times. Every loop in every language is built from the same three decisions: where the counter starts, when the loop stops, and what changes on each pass. Get the first wrong and your total is garbage. Get the second wrong and the program hangs. Leave out the third and the second can never happen.

What makes loops hard is that their behaviour is spread across time. You cannot see it by reading, because reading is one pass and the loop is many. So you make it visible: draw a table with one column per variable and one row per pass, then fill it in by executing the code in your head, one statement at a time. That is a dry run, and in Stage 0 the table is what earns the marks, not just the final number.

Every loop is three decisions — start, stop, step. If you cannot fill in a trace table for it by hand, you do not know what your loop does. You are hoping.

Pass (iteration)One complete run through the loop body. The two words mean the same thing. 4729 has four digits, so the digit-sum loop takes four passes.

AccumulatorA variable declared before the loop that carries a running result across passes. Declare it inside the body instead and it resets every pass.

Trace tableA table with one column per variable and one row per pass, filled in by hand. It is how you prove what a loop does without running it.

02 Worked example

Sum the digits of 4729, on paper

The loop takes the last digit off 4729 and adds it to a running total, then throws that digit away. Three columns, one per variable: n, digit and sum. Each row holds the values at the end of that pass, so the n column already has the digit removed. The pink column is the digit destroyed on that pass.

passndigitsumwhat the pass did

start4729·0initialisation — sum starts at 0, nothing removed yet

1472994729 % 10 = 9, sum = 0 + 9, n = 4729 / 10 = 472

247211472 % 10 = 2, sum = 9 + 2, n = 47

3471847 % 10 = 7, sum = 11 + 7, n = 4

404224 % 10 = 4, sum = 18 + 4, n = 0

check0·220 > 0 is false — the loop stops and prints 22

Write that last row down. The check that fails is part of the table, and leaving it out is the single most common way to drop marks on a dry-run question. Now read the sum and n columns together, row by row: 0 and 4729, then 9 and 472, then 11 and 47, then 18 and 4, then 22 and 0. The digits still sitting inside n plus the total already collected in sum add to 22 on every single row: 0+22, 9+13, 11+11, 18+4, 22+0. That sentence is a loop invariant. It is true at the top of every pass, which is why the loop is right for any number and not just this one.

03 Mechanics

while and for are the same three parts

These two programs are the same loop. Both print 22 for 4729, both take four passes, and both produce the trace table you just filled in. The only difference is where the three parts are written down.

while — the three parts scattered

n = 4729          // startsum = 0while n > 0:       // stop    digit = n % 10    sum = sum + digit    n = n / 10     // stepprint sum

for — the three parts in one header

sum = 0for (n = 4729; n > 0; n = n / 10):    digit = n % 10    sum = sum + digitprint sum

The three parts did not change, only their addresses did. Start is n = 4729, stop is n > 0, step is n = n / 10. On the left they sit on lines 1, 3 and 6 and you have to hunt for them. The for header puts all three side by side, which is why it is the usual spelling when you already know the pass count before you start — walking an array of length 5, say. For this loop either spelling is correct, and while reads more naturally, because you cannot say how many passes it needs until the digits are gone.

The step line is the one that ends the loop. Delete line 6 on the left and n stays 4729 for ever, so n > 0 stays true for ever. The for version makes that mistake visible: an empty third slot in the header is something you can see, a missing last line of a body is not.

A do-while moves the check below the body. Same three parts again, but tested after the first pass, so the body always runs at least once. Feed both versions n = 0: the while writes an empty trace table and prints 0, the do-while writes one row — digit = 0, sum = 0, n = 0 — and also prints 0. Same answer, different tables, and the table is what gets marked.

Off-by-one, counted rather than argued

Loop header	Values i actually takes	Passes
i = 0; i < 5	`0 1 2 3 4`	`5`
i = 0; i <= 5	`0 1 2 3 4 5`	`6`
i = 1; i <= 5	`1 2 3 4 5`	`5`
i = 1; i < 5	`1 2 3 4`	`4`
i = 5; i > 0; i--	`5 4 3 2 1`	`5`

Never count passes by reading the operator. Write out the values the counter actually takes, then count them. i = 0; i <= 5 looks like five passes and is six — and if i is indexing a five-element array, that sixth pass reads past the end.

05 Cheat sheet

Five constructs and the mistake each one invites

Construct	Body runs	The mistake it invites
`while (cond)`	0 or more times — checked before the first pass	Leaving out the step line, so cond can never turn false
`for (init; cond; step)`	0 or more times — the same three parts, one header	Changing the counter inside the body as well as in the header
`do { } while (cond)`	1 or more times — checked after the first pass	Using it when empty input must produce zero passes
`break`	Ends the loop now — no step, no further check	Breaking out of only the inner loop of a nested pair
`continue`	Skips the rest of the body — in a for the header step still runs, in a while nothing runs	In a while it skips the step line at the bottom, so the loop hangs

The body can run zero timesA while and a for both test before the first pass, so n = 0 gives a trace table with no pass rows at all and sum keeps its initial value 0. Only a do-while guarantees one row. This is the first thing an interviewer tests with empty input.

Digit loops are O(log n), not O(n)Dividing by 10 every pass means one pass per digit. 4729 takes 4 passes and a nine-digit number takes 9, because n has floor(log10 n) + 1 digits. Calling it O(n) would mean 4,729 passes.

An infinite loop is a missing step, not a wrong conditionwhile n > 0 is a fine condition. Delete n = n / 10 and it never ends. Name the variable in the condition, then find the line in the body that moves it toward false. If there is no such line, you have found the bug.

06 Where & why

A slow tool you will be graded on

A trace table is slow. Writing out four passes of a six-line loop takes about a minute by hand. That is the trade: it is the only way to be certain about a loop without running it, and in a written exam or a whiteboard round you cannot run anything.

Fill in a trace table when…

The question says dry runStage 0 marks the table, not the answer. A correct final value with no rows shown scores less than a complete table with one arithmetic slip in it.

There is an accumulatorAny variable that carries a value across passes — sum, product, count, rev — is where the bugs live. Giving it a column makes a wrong initial value obvious on the very first row.

The loop does not stopThree rows are enough. If no column moves in the direction the condition needs, you have found the infinite loop without waiting for the program to hang.

The output is off by one itemGive the counter its own column and write down the values it actually takes. Reading i < n against i <= n off the code is where people guess wrong; reading the column is where they get it right.

Use something else when…

Situation	Better choice	Why
The loop runs hundreds of passes	A print statement inside the body	A table is for reasoning about a handful of passes. Past about ten rows you are copying, not thinking, and copying is where the arithmetic slips creep in.
You need to know which pass broke it	A debugger breakpoint with a watch list	The debugger shows the same columns automatically and lets you jump to pass 500. It is a trace table that fills itself in.
The loop body calls other functions	Dry-run each function on its own first	A trace table has one column per variable in one scope. A nested call needs its own table, and stacking those tables is exactly what the call stack does.
You want to prove the loop is right for every input	An informal loop invariant	One sentence that stays true at the top of every pass covers all inputs at once. A table only proves the input you traced.

At work you will use a debugger, not paper. The habit still pays every day: when a code review changes < to <=, the fast reviewer is the one who names the values the counter now takes instead of arguing about the operator.

07 Interview questions

What they actually ask

First-round loop questions are almost never about syntax. They are about pass counts, about what a variable holds the moment the loop ends, and about whether you can dry-run something on a whiteboard with no compiler in the room.

What are the three parts of a loop?

Initialisation, condition and step. sum = 0 and n = 4729 run once before anything else, n > 0 is tested before every pass, and n = n / 10 runs at the end of every pass. A for puts all three in one header and a while scatters them, but all three always exist — if you cannot point at the step line, you have an infinite loop.

When would you use a while loop instead of a for loop?

When you do not know the number of passes before you start. Summing the digits of 4729 is the standard case: you cannot say it needs four passes until you have divided the digits away, so the natural spelling is "keep going while n > 0". Use a for when the count is known up front or the counter moves by a fixed arithmetic step.

What does a do-while give you that a while does not?

A guaranteed first pass, because the condition is tested after the body instead of before it. Feed both loops n = 0: the while writes a trace table with no pass rows and the do-while writes one. Reach for it when the body has to happen before there is anything to test — read a menu choice, then check whether it was valid.

How many times does for (i = 0; i <= n; i++) run?

n + 1 times, not n. Write out the values i actually takes — 0, 1, 2 … n — and count them. With i < n the list stops at n - 1 and there are n of them, which is why < is the correct operator for walking an array of length n.

What actually causes an infinite loop?

A condition that can never become false, which nearly always means the step is missing, moving the wrong way, or changing a different variable than the one being tested. Delete n = n / 10 from the digit-sum loop and n stays 4729 for ever. Find it on paper: name the variable in the condition, then find the line in the body that moves it toward false.

What is the difference between break and continue?

break leaves the loop immediately — no step, no further condition check. continue skips the rest of the body and jumps straight to the next condition check. The trap is continue inside a while, where the step line usually sits at the bottom of the body: continue jumps over it and the loop hangs. In a for the step lives in the header, so it still runs.

Dry-run this loop for me and show your table.

One column per variable plus a column for the condition, one row per pass, filled left to right in statement order. For 4729 the digit, sum and n columns read 9 / 9 / 472, then 2 / 11 / 47, then 7 / 18 / 4, then 4 / 22 / 0. Then write the row where n > 0 is false — that row is part of the answer and it is the one people leave out.

What is a loop invariant, informally?

One sentence that is true at the top of every pass, whatever the input. For the digit-sum loop it is "the digits still inside n plus the total already in sum always add up to the digit sum of the original number" — check it row by row as 0 + 22, 9 + 13, 11 + 11, 18 + 4, 22 + 0. A trace table proves one input; an invariant proves all of them.

Where do you declare the accumulator, and what breaks if you get it wrong?

Before the loop, never inside the body. Move sum = 0 inside and it resets on every pass, so 4729 prints 4 — the digit added on the last pass — instead of 22. The initial value matters too: 0 is right for a running sum and wrong for a running product, where it has to be 1.

What is the time complexity of the digit-sum loop?

Hard

Keep replacing n with the sum of its digits until a single digit is left, and return it — 4729 becomes 22, and 22 becomes 4.

Follow-up

The body of the outer loop is itself a loop, so you need one inner table per collapse plus an outer table with one row each. There is also a closed form for every n >= 1, namely 1 + (n - 1) mod 9, and making the loop and the formula agree on 4729, 9 and 18 is the real check. n = 0 is the one input the formula does not cover — its digital root is 0.

Show the hint

The outer condition is "n still has more than one digit", which is just n >= 10. Write the outer table first, one row per collapse, before you trace a single inner pass.