Chapter 4 Iteration

Up until this point, our programs have executed sequentially, proceeding one line at a time. In the previous chapter, we saw how to use if statements to skip or run certain lines, but even then, our program had just been “flowing forward” until the end. But what if we don’t want this? In particular, what if we want to execute something repeatedly? For example, imagine we go to the ATM to draw money. There is a program running on the ATM that asks us for our card and PIN, and then allows us to select options to withdraw money. Once we’re done, what happens next? Does the program finish running? No! It goes back to the beginning so that it’s ready for the next customer!

In this chapter, we’ll be looking at how to achieve this in a number of ways. This concept is known as iteration, but more informally looping. In most programming languages, there are three types of ways we can perform iteration. These are called while loops, do-while loops and for loops. In Python, however, there are only two! Therefore, we will only discuss while and for loops in this chapter, and leave the remaining one for later on.

4.1 While Loops

The while loop is the most fundamental looping construct in programming. In fact, all other loops are just while loops dressed up in more convenient forms! In psuedocode, the while loop looks like this:

  while logical_expression:
     statement_1
     statement_2

The while loop can be thought of as “As long as….” In other words, as long as the logical expression is true, execute the following lines of code. Therefore, the lines of code inside the while loop will be executed until the logical expression becomes false, at which point the program “escapes” from the loop and continues on with the next line of code. The code indented inside the while loop is known as the loop body.

Much like the if statement, we associate the lines of code that are to be executed repeatedly by using indentation. Any code that is “inside” the while loop will run repeatedly. In the example below, the statement_1 and statement_2 will be run repeatedly, but statement_3 will only be run once the loop has finished, since it is not inside loop body!

  while logical_expression:
     statement_1
     statement_2
  statement_3

As mentioned, the while loop will continue executing over and over again as long as logical_expression remains true. This has two implications: 1. If the logical expression never becomes false, then the loop will run forever! This is known as an infinite loop, and is not desirable for obvious reasons. 2. If the logical expression is immediately false, then the loop immediately exits, and the loop body will never execute (not even once).

Humour side quest! There is a very old computer science joke that goes as follows:

A programmer went to the grocery store. His wife said, “While you are out, buy some milk.” He never came home.

Now, it’s not the funniest joke in the world, but before moving on, make sure that you understand it!

Let’s look at an example by considering the following program:

i = 0
while i < 100:
   print(i, '\t', i * i)
   i = i + 1
print("Done.")


History side quest! The above program is actually a very famous program. It was written for the EDSAC computer by a man names David Wheeler, who became the first person to be awarded a PhD in computer science! Use the internet to find out more information about this program and other early computer programs.

4.1.1 Count-controlled repetition

Let’s look at a problem that could benefit from the use of while loops:

A class of ten students took a test. The grades (integers in the range 0 to 100) for this test are available to you. Determine the class average.

As a programmer, when faced with a problem such as the above, the first step is not to sit down and start writing code immediately! First, we must determine the problem to be solved, and then break the problem into smaller and smaller subproblems until we have a solution. This refinement process might happen on paper, or if we are experienced enough, in our head. In any case, once we have done that and have the solution to the problem, only then are we ready to start programming. Let’s look at how we might develop a solution in pseudocde to the problem.

Top-level pseudocode:

  Determine the class average of the test.

Well that was straightforward, but now we need to ask how we’re going to do that? This leads to our first refinement:

First refinement:

  Input the ten test grades
  Sum them up
  Calculate the average
  Output the average

Okay, so now we have a better idea of how to do this. The first two steps are still tricky though. How do we achieve them? One way would be to just have ten input statements! But we’re lazy, and we don’t want to write that much code (plus, what if the question asked for 1000 students?!) So instead we can use our new idea of iteration to loop ten times to get the input and sum it up.
Since we know we need to do it ten times, we need some kind of counter to let us know when we’ve reached ten, so we can stop. Also, when summing numbers, we can keep track of the sum seen so far (starting at zero), and every time we get a new number we just add it to this sum. Therefore, our new pseudocode might look like this.

Second refinement:

  set the sum to 0
  set the counter to 0
  while the counter is less than 10
     input next grade
     add grade to sum
     add 1 to counter
  set average to sum / 10
  output average

Note that because we started counting from 0, to count ten times we go from 0 to 9 (and so the logical expression is strictly less than). Now that we have our pseudocode, we are ready to start programming!

Question! Convert the above pseudocode into a Python program. Run it on your computer and test it with some input to make sure it’s working.

4.1.2 Sentinel-controlled repetition

In the above example, we knew how many times to loop. But what if that’s not the case. To handle this, we need some kind of flag or special case to tell us when to stop. This flag is known as a sentinel value. The loop will continue to run until the sentinel value is encountered, at which point it will stop looping. For example, we might write a program that allows the user to enter as many marks as they want, and tells them that they should enter a special value (e.g. -1) to stop! Modifying the above psuedocode to support this, our new pseudocode may look as follows:

  set the sentinel to -1
  set the sum to 0
  set the counter to 0
  input a grade
  while the grade is not the sentinel
     add grade to sum
     add 1 to counter
     input a grade
     
  set average to sum / counter
  output average

Note that in general, the sentinel is just an arbitrary value. In this example, we have chosen -1 since it is not a valid mark and so is a clear indication that the user wants us to stop.

Question! Considering the above example, why would 0 be a poor choice for a sentinel value?

Question! Convert the above pseudocode into a Python program. Run it on your computer and test it with some input to make sure it’s working.

Question! Is the above pseudocode actually correct?! Try find an edge case where it produces wrong or unexpected output, and then modify the code to fix it! (Hint: computing the average involves division. When is division dangerous?)

4.1.3 Nested control statements

Just like if statements, we can put any number of statements inside the body of a loop. Therfore, we could have loops inside loops (nested loops), if statements inside loops, loops inside if statements, etc. Let’s look at a quick example these nested control statements. As previously, we’ll take the problem, break it down into refined pseudocode, and then finally write the code in Python.

Write a program that would count and display the number of students that have passed and the number of students that have failed from a list of exam results for 10 students. If more than 8 students have passed, display “Bonus to lecturer!”

Top-level pseudocode:

  Accept exam results
  Display results
  Decide if lecturer should receive a bonus

How should this bonus be decided? According to this problem, it’s based on the number of people who have passed. So we must compute that number.

First refinement:

  Input the 10 exam grades
  Count passes and failures
  Display a summary of results
  Decide on bonus

Try break this pseudocode down even further, and then see if your solution lines up with the pseudocode below. Remember, there is more than one way to arrive at the correct answer.

Second refinement:

  set the passes to 0
  set failures to 0
  set counter to 0
  while counter < 10
     input exam result
     if result > 50
        add 1 to passes
     else
        add 1 to failures
     add 1 to counter
  display passes
  display failures
  if more than 8 passes
     display "Bonus!"

The equivalent Python code is as follows:

passes = 0
failures = 0
n_students = 0
while n_students < 10:
   mark = int(input())
   if mark >= 50:
      passes = passes + 1
   else:
      failures = failures + 1
   n_students = n_students + 1
print("Passes", passes)
print("Failures", failures)
if passes > 8:
   print("Bonus!")

Notice how similar the Python code is to the pseudocode. The takeaway here is that once you have your pseudocode mapped out and in place, you’re basically done! Converting to Python is a much easier job!

4.2 For loops

In the previous examples, we wanted to count to some number. This counting procedure is a very common occurrent and requires three things:

  1. The initialisation of a counter.
  2. The termination condition (i.e. when to stop).
  3. The modification of the counter (i.e. how the counter should change every time).

While this can be achieved with while loops, it is slightly inconvenient. Because this is such a common requirement in programming, for loops were developed as a convenient way of doing so. Let’s look at the code above, and how we would instead write the same thing using a for loop instead.


passes = 0
failures = 0
# the for loop is below
for n_students in range(0, 10, 1):
   mark = int(input())
   if mark >= 50:
      passes = passes + 1
   else:
      failures = failures + 1
print("Passes", passes)
print("Failures", failures)
if passes > 8:
   print("Bonus!")

4.2.1 Python Ranges

In Python, for loops are particularly straightforward to write because of the ability to define ranges. A range produces a sequence of integers between a start and end point (much like a range or interval in mathematics). In Python, the general form of a for loop is as follows:

for counter_name in range(start, stop, step):
   statement_1
   statement_2
   ...

The counter_name is a variable name for our counter. We could choose any name we want (common ones you will see are i and j). The range gives us a sequence of integers from start to stop (exclusive of stop). step tells Python how much to increment the counter by each time (e.g should we go in steps of 1 or 2?) In Python, we can leave out either or both of start and step values if we wish. If we do that, they will take their default values, which are start = 0 and step = 1. Below are some examples of range definitions and the range of integers they produce.

Python statement Range of integers
range(0, 3, 1) \([0, 1, 2]\)
range(5) \([0, 1, 2, 3, 4]\)
range(0, 10, 2) \([0, 2, 4, 6, 8]\)
range(20, 25) \([20, 21,22, 23,24]\)
range(5, 2, -1) \([5,4,3]\)

Question! Write a program that accepts a positive integer \(N\) and outputs \(\sum\limits_{i=1}^N i\).

Question! Write a program that, when run, produces the following output:

1

22

333

4444

55555

666666

7777777

88888888

999999999

Question! A person invests R1000.00 in a savings account yielding 5% interest annually. Assuming that all interest is left on deposit in the account, calculate and print the amount of money in the account at the end of each year for 10 years. Use the following formula for determining these amounts:

\[a = p(1 + r)^n\]

where

\(p\) is the original amount invested (the principal)

\(r\) is the annual interest rate

\(n\) is the number of years

\(a\) is the amount on deposit at the end of the \(n\)th year

4.3 Break and Continue

A final related concept related to loops are the two statements break and continue. These allow us to modify how the loop works from within the body of the loop itself. The break statements forces the loop to quit, regardless of whether it has in fact completed! We can think if this as a kind of “force escape” statement — immediately exit the loop I am in!

In the example below, we have an example of an infinite loop, since the logical expression is always true.

i = 0
while True:
   print(i)
   i = i + 1

We can use the break statement to exit the loop.

i = 0
while True:
   print(i)
   if i > 10:
      # as soon as i > 10, let's get out of here!
      break
   i = i + 1

The continue statement, on the other hand, allows us to skip the statements in the rest of the loop body, but continue with the loop otherwise. An example of this is below.

for i in range(0, 10):
   if i == 5:
      continue  # go to the start of the loop and continue
   print(i)

If you run this code, you will see that it prints out every number from \(0\) to \(9\), except \(5\). Make sure you understand why this happens.

It is important to note that, while break and continue help us modify loops in various ways, we can often write code in such as way that we never need to use them. It is good practice to keep the use of these statements to a bare minimum.