My account Contact me

COMP 202 Foundations of Programming • McGill University, Montreal

Revision sheet: Loops and the patterns they carry (COMP 202)

This sheet is not a summary of the loops chapter of COMP 202: you have the slides and the textbook. It answers one question, what loses marks on loops in a COMP 202 assessment at McGill University, on paper at the midterm and under the autograder on an assignment, and which precise gesture avoids each loss.

The angle of the chapter is that a loop is decided before a line is written. The mechanics of for and while are learnt in an afternoon; the marks go on the day the loop hangs, because a test reads a variable that nothing changes, or ends one pass too early, because a counter was created on the wrong side of the header. Every trap below is written as the line a student actually wrote, next to the line to write instead, with what it costs.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next and tells you which chapter to tackle next. Create your space, an email is enough.

The thread of the chapter

A loop is decided before it is written, on what you already know: a known number of passes is a for, a stopping condition alone is a while. Every loop that never ends in this course is the same sentence in a different costume, a test that reads a variable no line of the body changes, and every loop that ends on the wrong value is an accumulator created, updated or read in the wrong one of its three places.

This chapter is part of COMP 202, Foundations of Programming (McGill)

The essentials

One question before writing: do I know the number of passes?

  • • Yes, a number or a collection: a for loop. The header creates the counter, tests it and advances it, so none of the three can be forgotten. for i in range(n) makes exactly n passes, i from 0 to n - 1, and the last value is n - 1, never n.
  • • No, only a condition to stop on: a while loop. The header only tests, so the body carries the responsibility of changing what the test reads, and that update belongs on the LAST line of the body.
  • • A while loop tests BEFORE its first pass: a condition false at the start gives a body that runs zero times, with every variable still at its starting value. Python has no do while; the shape for at least one pass is while True with a break right after the read.
  • • When the number of passes is the ANSWER, the loop is a while with a counter: how many months until the balance passes 10 000, how many steps until the sequence reaches 1. A for over a guessed bound is a while wearing a for header, and it lies the day the guess is too small.
  • • Nested loops multiply: an inner range(4) inside an outer range(3) runs the inner body 12 times, and an inner range(i) inside an outer range(n) runs it n(n−1)/2n(n-1)/2 times.
i = 0 (before the loop)i < 5 ?body of the loopi = i + 1 (last line)after the looptruefalseback to the testthe test reads i,so the body must change i
The test reads i and the only way back to the test is through the last line of the body: if that line is missing, or skipped by a continue, the loop never ends.

On a paper question that asks for a loop, write the reason for the form in one comment, for example: while, because the number of lines depends on the user. Markers give a method mark for it, and it stops you from writing for i in range(100) around a menu.

The accumulator: three places, and the value that starts it

  • • Created BEFORE the loop, once. Updated INSIDE, once per pass. Read AFTER. A variable set to zero at the top of the body is a new variable on every pass and can never hold more than one pass.
  • • The starting value is neutral for the update: 0 for a count or a sum, 1 for a product, True for a claim about every element, False for a claim about at least one, the first element itself for a largest or a smallest.
  • • A flag only ever moves once and in one direction: every starts True and can only fall, at least one starts False and can only rise. A flag that goes back and forth is answering a question about the LAST element only.
  • • A search stops on its first hit with a break, and what it returns when nothing is found is decided before the loop: -1 for an index, None otherwise, and the caller tests it.
  • • After the loop, an average divides by the count, and the count can be 0: the guard if count == 0 is written before the division, not after the crash.

The line that updates the accumulator sits inside the loop, indented one level from the header; the line that prints it sits after the loop, at the level of the header. One indentation level too many prints a running total on every pass, one too few counts only the last element.

The rules in table form

Each row reads from left to right: the assumptions, then the result. A red cell is not an answer, it is the finding that the form settles nothing and the instruction to rewrite it. Every case is followed by a worked example.

The accumulator family: the question asked picks the starting value

Read the question in the statement, then the row: the last column is the value the variable must hold before the loop starts. The red rows are starting values copied from real papers; a red cell is not a value, it is an order to look up the neutral element of the update.

Question askedUpdate in the bodyStarting value
how many count = count + 1 0

Example: the vowels of programming: count ends at 3, and at 0 for an empty string.

the total total = total + v 0

Example: the marks 70, 55, 90 give total 215; an empty list gives 0, which is right.

the product product = product * v 1

Example: the list 2, 3, 4 gives 24; an empty list gives 1, the empty product.

is every one if not ok: flag = False True

Example: are 3, 1, 4 all positive: True stays True; 3, -1 falls to False on the second pass.

is there one if ok: flag = True False

Example: is any of 3, -1 negative: False rises to True on the second pass.

the largest if v > best: best = v the first element

Example: the largest of -7, -3, -9 is -3, found only when best starts at -7.

the product product = product * v 0 not a neutral value

Example: with product = 0, the list 2, 3, 4 gives 0 instead of 24, and so does every other list.

What to do: Start at the neutral element of the update: 1 for a multiplication, since 1 times anything is that thing.

is every one if ok: flag = True False answers another question

Example: are 3, -1 all positive: starting False and rising on 3 ends True, which is the answer to is there one.

What to do: A flag for every starts True and only falls; write the update on the element that BREAKS the claim, if v <= 0: flag = False.

Every starting value is the value the loop must return on an empty collection, which is why 0 marks and 0 sum are right, 1 product is right, and a largest of an empty list has no value at all: that case is refused before the loop, never seeded with 0.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. A while loop whose body never changes what the test reads

the whole question on paper; on an assignment the autograder times out, and every test of that function is marked 0

What not to write

“choice = input('Choice: ') then while choice != 'q': and the cascade of ifs, then print('bye'). It works, I typed q and it stopped.”

What to write

“The body must re-read choice, on its last line: choice = input('Choice: ') inside the loop, after the cascade. Or while True: with the read first and if choice == 'q': break right after it.”

Why: It stopped for you because you typed q FIRST. On any other input the test reads the same value for ever, since nothing in the body assigns to choice. The check takes five seconds and needs no computer: name the variable in the condition, then find the line of the body that changes it. No line, no exit.

2. A continue written above the update of a while loop

the whole question, and an autograder timeout on the first input that contains a space

What not to write

“i = 0, while i < len(word): if word[i] == ' ': continue, then the processing, then i = i + 1 as the last line.”

What to write

“Increment BEFORE the continue, or use for i in range(len(word)) so that the update lives in the header where no continue can skip it.”

Why: continue jumps straight back to the test without running the lines below it, and the update is one of those lines. On the first space, i stops moving and the same character is tested for ever. In a for loop the same continue is harmless, which is one more reason to write the for whenever the count is known.

3. The counter created inside the loop it is meant to count

3 to 4 marks out of 10, since the loop is otherwise correct and the printed value is wrong on every input

What not to write

“while True: done = 0, then choice = input(...), if choice == 'q': break, if choice in 'ab': done = done + 1. After the loop print(done).”

What to write

“done = 0 goes BEFORE the while, once; inside, only done = done + 1; after the loop, print(done).”

passchoice readdone, created beforedone, created inside1a112b213x204a31same four choices, same loop, two places for done = 0printed after the loop: 3 on the left, 1 on the right
Same loop, same four choices: the counter created before the loop climbs to 3, the one created inside restarts at 0 on every pass and never exceeds 1.

Why: A variable assigned at the top of the body is recreated on every pass, so it can only hold the count for the current pass: the program prints 0 or 1 whatever the user typed. The figure runs the two placements on the same four choices.

4. A flag for every started on the side of at least one

the whole question: the code answers a different question

What not to write

“all_positive = False, then for v in values: if v > 0: all_positive = True.”

What to write

“all_positive = True, then for v in values: if v <= 0: all_positive = False. The flag starts true because nothing has contradicted it yet, and one counterexample brings it down for good.”

Why: Started False and raised on a positive element, the flag answers is there at least one positive number: on the list 3, -1 it ends True. A flag for every is initialised True and updated on the element that BREAKS the claim, a flag for at least one is initialised False and updated on the element that PROVES it.

5. Counting the numbers when the loop counts the arrows

1 to 2 marks on a trace question, and it repeats on every counting loop of the exam

What not to write

“From 6 the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1, so the program prints 9.”

What to write

“steps is incremented once per pass and a pass is one arrow: nine numbers, eight arrows, the program prints 8.”

61321035416586472819 numbers in the sequence8 arrows: the loop runs 8 times and prints 8
Nine boxes, eight arrows: the body of while n != 1 runs once per arrow, so the counter ends at 8, not 9.

Why: The counter lives in the body, and the body runs once per TRANSITION, not once per value: the starting value was there before the first pass and 1 is reached by the last one, but no pass runs after it. Writing the sequence WITH its arrows, as in the figure, settles every question of this kind.

6. Reading break as an exit from every enclosing loop

2 to 3 marks on a trace, the whole question when the program must print the FIRST position only

What not to write

“The break in the inner loop stops the search, so as soon as the value is found the program prints one line and moves on.”

What to write

“break leaves the innermost loop only; the outer loop starts its next pass. To leave both, put the loops in a function and return, or set found = True and test it right after the inner loop.”

Why: Python has no labelled break. Two for loops over range(3) with a break in the inner one when j == 0 still print three lines, one per pass of the OUTER loop. The clean exit from a double loop is return inside a function, which leaves everything at once and hands back the answer.

7. Assigning to the loop variable to stop a for loop

the whole question when the loop was meant to stop, and sometimes an IndexError on top of it

What not to write

“for i in range(10): if values[i] == target: i = 20, so that the loop stops.”

What to write

“Assigning to i does nothing to the loop: the header hands i the next value of range at the top of every pass. Write break, and the position you want to keep goes in another variable, position = i, before it.”

Why: The for header assigns the next value of range to i at the start of each pass, throwing away whatever the body left there: the loop prints 0 to 9 unchanged. A for cannot be stopped by touching its counter, only by break; a while can, and that is exactly why a while is easier to hang.

8. A strict stopping condition on a value that can step over the target

the whole question, and an autograder timeout

What not to write

“x = 0.0, while x != 1.0: x = x + 0.1, and it counts up to one in ten passes.”

What to write

“Ten additions of 0.1 give 0.9999999999999999, which is not 1.0, so the loop never ends. Write while x < 1.0, or count the ten steps with for k in range(10) and compute x = k * 0.1.”

Why: One tenth has no finite binary expansion, so every addition carries a rounding error and the sum lands beside 1.0, not on it; from there x grows for ever. The same shape hangs on integers: while n != 0 with n = n // 10 on a negative n sticks at -1. An inequality tolerates the values you did not think of; a strict difference demands an exact landing.

9. A float handed to range as a bound

the whole question: TypeError before the first pass

What not to write

“for d in range(2, n ** 0.5): if n % d == 0: ...”

What to write

“range takes integers only: for d in range(2, int(n ** 0.5) + 1), or math.isqrt(n) + 1, with the + 1 because range excludes its bound and the square root itself must be tested.”

Why: n ** 0.5 is a float even when n is a perfect square, and range refuses it. The + 1 is not decoration: 49 has 7 as its only nontrivial divisor, and range(2, 7) stops at 6, so without it 49 is declared prime.

Which method to choose

Which loop, from what the statement gives you

Before writing the header, say out loud what you know about the number of passes

  • If a number of passes, or a collection to walk → for over range(n), or for over the collection itself; never a counter by hand

    Example: for month in range(48), for ch in word

  • If only a condition to stop on, met an unknown number of passes later → while, with the line that changes the tested variable as the LAST line of the body

    Example: while balance < 10000: ... then month = month + 1

  • If at least one pass, then decide on what was read → while True: read first, if the exit value: break, then act on the value

    Example: a menu, a mark asked until it is valid

    the exit test sits right under the read, never buried in a branch

  • If the number of passes IS the answer → while with a counter incremented once per pass, read after the loop with the final value

    Example: month 47, with the balance 10158.06 that goes with it

  • If the passes cannot be bounded at all → while, plus a guard on the input BEFORE the loop, because the exit condition is only meaningful for valid data

    Example: while n != 1 after if n < 1: refuse; n = 0 would cycle for ever

  • If a pair of things to compare, every pair once → for i over range(n), for j over range(i + 1, n): the inner loop starts after i

    Example: n(n−1)/2n(n-1)/2 pairs, 10 for five items

No branch fits a for loop over a guessed bound with a break inside: that is a while written twice. If you catch yourself writing range(1000) around a condition, cross it out and write the while.

Which exit, from what the loop must do at that moment

Say what must happen to the CURRENT pass and to the loops around it

  • If stop this loop at once on a hit → break, and record what you need in another variable just before it

    Example: position = i then break

  • If skip this element only and go on with the next → continue in a for; in a while, move the update ABOVE the continue or turn the loop into a for

    Example: skip the spaces of a string

  • If leave two nested loops at once → put the loops in a function and return the answer; failing that a flag tested right after the inner loop

    Example: return (i, j) from inside the inner loop

  • If say that nothing was found → a flag found = False set True beside the break, tested after the loop; the loop else does the same and is misread by most readers

    Example: if not found: print('not in the list')

  • If finish the current pass, then stop → make the condition false and let the pass run to its end; break would cut it short

    Example: an invalid value processed once before the exit

In COMP 202, the flag version is the one to submit: every reader understands it, and it survives being moved into a function. The else of a loop is worth knowing to READ a trace question, not to write.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Writing a sentinel loop that a marker and an autograder both accept

When to use it: The statement says read until, keep asking until, stop when the user types: the number of passes depends on the input.

  1. 1 Read ONCE before the loop, into the variable the condition will test, and write the condition on that variable: while mark >= 0, not while True unless the read comes first inside.
  2. 2 Create every accumulator before the header, with its neutral value written and justified in a comment: count = 0, total = 0, all_pass = True because nothing has failed yet.
  3. 3 Update each accumulator once per pass, inside the loop, and keep the flag update on the element that breaks the claim.
  4. 4 Re-read the variable of the condition on the LAST line of the body, with the same prompt as the first read.
  5. 5 After the loop, guard whatever divides by the count with if count == 0, then print or return the results, at the indentation of the header.
  6. 6 Trace the loop on paper with three values and the sentinel, one row per pass, and check the zero-pass case: the sentinel typed first.

Concluding sentence

“The loop ends because mark is re-read on the last line of the body, so the test sees a new value on every pass; with the sentinel typed first the body runs zero times and count stays 0, which the guard handles.”

The trap: Re-reading at the TOP of the body: the value just read is then overwritten before it is counted, and the first mark is lost.

Marking: Typically 1 mark for the loop form, 1 for the read before the loop, 2 for the accumulators with their starting values, 1 for the re-read, 1 for the guard on the empty case.

Tracing a loop on paper, the way the marker reads it

When to use it: The question shows five to ten lines and asks what is printed, how many times the body runs, or the final value of a variable.

  1. 1 Draw a table with one column per variable, one column for the value of the condition, and one for what is printed.
  2. 2 Fill one ROW per pass, evaluating the condition first: a first row whose condition is False means zero passes, and the variables keep their starting values.
  3. 3 Apply the lines of the body in order, and on a continue or a break write which lines were skipped in that row.
  4. 4 Write the row where the condition becomes False, and read the answer from THAT row, not from the previous one.
  5. 5 Count the rows for the number of passes, and count the printed column for the output: they differ whenever a print sits after the loop or inside a branch.

Concluding sentence

“The body runs 4 times; after the fourth pass n is 0, the test n > 0 fails, and the program prints 10.”

The trap: Reading the answer from the last row where the body ran instead of the row where the test failed: the two differ by one update.

Marking: Typically 1 mark per correct row on a five-row trace, and the final value is only paid if the exit row is shown.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

The typical problem, taken apart

Marks read until a negative number: count, average, and every mark at least 60

Write a program that reads integer marks until the user types a negative number, then prints how many marks were read, their average, and whether every mark was at least 60. The negative number is not a mark.

Show the trace of your program on the input 70, 55, 90, -1, and say what it prints when -1 is typed first.

Python
mark = int(input('Mark (negative to stop): '))
count = 0
total = 0
all_pass = True
while mark >= 0:
    count = count + 1
    total = total + mark
    if mark < 60:
        all_pass = False
    mark = int(input('Mark (negative to stop): '))
if count == 0:
    print('no marks')
else:
    print(count, total / count, all_pass)

Step 1

Decide the form: the number of marks depends on the user, so the loop is a while, and its condition is on the mark just read, mark >= 0. The first read happens BEFORE the header, so the test has a value to look at.

Why

Writing the reason for the form is the method mark, and it rules out a for over a guessed count. Reading before the loop is what makes the zero-pass case work: the sentinel typed first is seen by the test, not counted by the body.

Step 2

Create the three accumulators before the loop with their neutral values: count = 0, total = 0, and all_pass = True because no mark has failed yet.

Why

Placed inside the loop they would restart on every pass. The flag starts True because it answers every mark: it can only fall, and it falls on the element that breaks the claim, mark < 60.

Step 3

Body, in order: count and total are updated, the flag falls if mark < 60, and the LAST line re-reads mark with the same prompt.

Why

The re-read is the line that gives the test something new to look at; on the last line, the mark just read has been counted before it is replaced. Re-reading at the top would lose the first mark.

Step 4

Trace on 70, 55, 90, -1: pass 1 reads 70 at the test, count 1, total 70, all_pass True, re-reads 55; pass 2, count 2, total 125, all_pass falls to False, re-reads 90; pass 3, count 3, total 215, re-reads -1; the test -1 >= 0 is False and the loop exits.

passmark at the testcounttotalall_passmark re-read170170True552552125False903903215False-1test-1 >= 0 is False3215Falseexitinput 70, 55, 90, -1: one row per pass, the last row is the exit

Why

One row per pass, the condition evaluated first, and the answer read from the exit row: 3 marks, average 215 / 3, that is 71.67, and all_pass False because of the 55.

Step 5

After the loop, at the indentation of the header: if count == 0 print no marks, else print count, total / count and all_pass. With -1 typed first the body runs zero times, count is 0, and the guard prints no marks instead of crashing.

Why

The division by count is the one line of the program that can crash, and it crashes exactly on the input a marker tries first. The guard is the empty-case mark of the question.

The conclusion, written out

“On 70, 55, 90, -1 the program prints 3 71.66666666666667 False: three marks, average 215 / 3, and not every mark reached 60. With -1 typed first it prints no marks, since the body never runs and count stays 0.”

The classic mistake on this problem: Re-reading mark at the TOP of the body, so that the first mark is overwritten before it is counted, and the sentinel itself is added to the total on the last pass.

Learn by heart

  • • for when the number of passes is known before the loop, while when only the stopping condition is.
  • • for i in range(n): n passes, i from 0 to n - 1. range takes integers only.
  • • A while tests BEFORE its first pass: zero passes is a case to check. Python has no do while.
  • • The line that changes the tested variable is the LAST line of the while body, and no continue sits above it.
  • • Accumulator: created before, updated inside, read after. Neutral start: 0 count or sum, 1 product, True every, False at least one, first element for a largest.
  • • break leaves the innermost loop only; to leave two, return from a function.
  • • A counter incremented once per pass counts the ARROWS of a sequence, not its numbers.
  • • Nested loops multiply: range(3) inside range(4) runs the inner body 12 times; range(i) inside range(n) runs it n(n−1)/2n(n-1)/2 times.

Frequently asked questions

When should I use a while loop instead of a for loop in Python?

Use a for loop when you know the number of passes before the loop starts, either as a number or as a collection to walk. Use a while loop when you only know the condition that stops it, for example reading until the user types quit or halving a number until it reaches one. If the number of passes is the answer to the question, it is always a while loop with a counter.

Why does my while loop never end?

Because the condition reads a variable that no line of the body changes, or because a continue jumps back to the test before the line that changes it. Underline the variable in the condition, then find the assignment to it inside the body and make sure it is the last line. A menu loop hangs when the second input is missing inside the loop.

Does break exit all nested loops in Python?

No. A break leaves only the innermost loop that contains it, and the outer loop simply moves on to its next pass. Python has no labelled break. To leave two loops at once, put them inside a function and use return, which also hands back the answer, or set a flag beside the break and test it right after the inner loop.

Why does my counter always print 0 or 1 after a loop?

Because the counter is created inside the loop, so it is reset to zero at the start of every pass and can only record the current pass. Create it once before the loop header, update it inside the loop, and print it after the loop, at the same indentation as the header. The three places are what makes an accumulator work.

What does else do after a for loop in Python?

The else of a loop runs when the loop finished without meeting a break, so it is a way of saying that nothing was found in a search. It does not mean the loop did not run. In COMP 202 the flag version is safer to write, a variable found set to True beside the break and tested after the loop, because every reader understands it at once.

Practise it

Corrected exercises: Loops and the patterns they carry, COMP 202

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

  • 10 corrected exercises
  • 100 points
  • 150 minutes
Do the exercises
Previous sheet Types, conversion and conditions Next sheet Strings and text processing

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/comp202-loops-and-patterns. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

See also

All revision sheets All exercise sets Computer science tutoring

Stuck in COMP 202?

I tutor COMP 202 at McGill in English or in French, in person in Montreal or online. Get in touch for a first session: we trace your own loops on paper until the infinite ones become visible before you run them.

Book a session WhatsApp
Site by Studio Squalli