Iteration with for

Estimated time to complete: one hour.

Introduction

The last fundamental tool for describing algorithms is iteration or “looping”: tasks that repeat the same sequence of actions repeatedly, with possible variation like using different input values at each repetition.

In Python — as in most programming languages — there are two versions:

  • when the number of iterations to be done is determined before we start — done with for loops;

  • when we must decide “on the fly” whether we are finished by checking some conditions as part of each repetition — done with while loops.

This Unit covers the first case, of for loops; the more flexible while loops will be introduced in Unit 6.

Repeating a predetermined number of times, with for loops

We can apply the same sequence of commands for each of a list of values by using a for statement, followed by an indented list of statements.

Example A

We can compute the square roots of several numbers. Here I give those numbers in a tuple (i.e., in parentheses). They could just as well be in a list [i.e., in brackets.]

import math
for x in (1, 2, 4, 9, 20, 1000000, 3141592653589793, 121):
    square_root_of_x = math.sqrt(x)
    print(f'The square root of {x:g} is {square_root_of_x:g}')
The square root of 1 is 1
The square root of 2 is 1.41421
The square root of 4 is 2
The square root of 9 is 3
The square root of 20 is 4.47214
The square root of 1e+06 is 1000
The square root of 3.14159e+15 is 5.60499e+07
The square root of 121 is 11

Aside A: Usingimport moduleinstead offrom module import object

Note the way that I handled importing from a module this time: the import statement just specifies that the module is wanted, and then I refer to each item used from it by its “full name”, prefixed by the module name, connected with a period.

This is often the recommended way to do things in larger collections of code, because it makes immediately clear where the object (here sqrt) comes from, without having to look up to the top of the file to check the import statement. On the other hand, the from module import item syntax is slightly more compact, and makes things read more like usual mathematical notation. So especially with mathematical objects like sqrt or pi where the name is fairly unambiguous, I typically use this shorter form.

Aside B: Controlling the appearance of printed output

Note also the new way that I inserted the values of the variables x and square_root_of_x into the string of text to be printed. Each :g appended in the {...} specified using the general (“g”) format for a real number: with this, large enough values (like 1000000) get displayed in scientific notation (with an exponent) to save space.

Later we will see refinements of this output format control, like specifying how many significant digits or correct decimal places are displayed, and ensuring that values on successive lines appear neatly aligned in columns: for more information, see the supplementary notes on formatted output and text string manipulation.

Repeating for a range of equally spaced integers with range()

One very common choice for the values to use in a for loop is a range of consecutive integers, or more generally, equally spaced integers. The first n natural numbers are given by range(n) — remember that for Python, the natural numbers start with 0, so this range is the semi-open interval of integers \([0,n) = \{i: 0 \leq i < n\}\), and so \(n\) is the first value not in the range!

Example B

Let’s combine this with a previous example:

for n in range(8):
    if n % 4 == 0:
        print(f'{n} is a multiple of 4')
    elif  n % 2 == 0:
        # A multiple of 2 but not of 4, or we would have stopped with the above "match".
        print(f'{n} is an odd multiple of 2')
    else:
        print(f'{n} is odd')
0 is a multiple of 4
1 is odd
2 is an odd multiple of 2
3 is odd
4 is a multiple of 4
5 is odd
6 is an odd multiple of 2
7 is odd

Ranges that start elsewhere

To specify a range of integers starting at integer \(m\) instead of at zero, use

range(m, n)

Again, the terminal value n is the first value not in the range, so this gives \([m, n) = \{i: m \leq i < n\}\)

Example C

for i in range(10, 15):
        print(f'{i} cubed is {i**3}')
10 cubed is 1000
11 cubed is 1331
12 cubed is 1728
13 cubed is 2197
14 cubed is 2744

Aside C: yet more on formatting printed output

Note that in the stuff to insert into the text string for printing, each item can be an expression (a formula), which gets evaluated to produce the value to be printed.

Ranges of equally-spaced integers

The final, most general use of the function range is generating integers with equal spacing other than 1, by giving it three arguments:

range(start, stop, increment)

So to generate just even integers, specify a spacing of two:

Example D

for even in range(0, 10, 2):
        print(f'2^{even} = {2**even}')
2^0 = 1
2^2 = 4
2^4 = 16
2^6 = 64
2^8 = 256

Brief Exercise A

Even though the first argument has the “default” of zero, I did not omit it here: what would happen if I did so?

Decreasing sequences of integers

We sometimes want to count down, which is done by using a negative value for the increment in function range.

Example E

Before running the following code, work out what it will do — this might be a bit surprising at first.

for n in range(10, 0, -1):
        print(f'{n} seconds')
10 seconds
9 seconds
8 seconds
7 seconds
6 seconds
5 seconds
4 seconds
3 seconds
2 seconds
1 seconds

Brief Exercise B

What is the last output, and why?

Example F: The first n factorials

I will illustrate two methods; with and without using an array to store the values.

# We first need a value for n.
# It will be the input argument to the function for each method.
n = 5
"""
Method 1: producing a numpy array of the factorials after displaying them one at a time.

We need to create an array of the desired length before we compute the values that go into it,
and one strategy is to create an initially empty array.
By default array elements are real numbers rather than integers,
so here see how to specify integers, with optional argument `dtype=int`)
Aside: another option is complex numbers: `dtype=complex`.
"""

import numpy

# Create a numpy array of n integers, values not yet specified:
factorials = numpy.empty(n, dtype=int)

factorials[0] = 1
print(f"0! = {factorials[0]}")
for i in range(1,n):
    factorials[i] = factorials[i-1] * i
    print(f"{i}! = {factorials[i]}")
print(f"The whole array is {factorials}")
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
The whole array is [ 1  1  2  6 24]

Note that if we just want to print them one at a time inside the for loop, we do not need the array; we can just keep track of the most recent value:

"""
Method 2: storing just the most recent value[s] needed.
"""
i_factorial = 1
print(f"0! = {i_factorial}")
for i in range(1,n):
    i_factorial *= i  # Note: this "*=" notation gives a short-hand for "i_factorial = i_factorial * i"
    print(f"{i}! = {i_factorial}")
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24

Aside C: The shorthands +=, *=, -= etc.

In the above code, the notation

`i_factorial *= i`

means

`i_factorial = i_factorial * i`.

The same pattern works for many arithmetic operators, so that for example

sum += f(x)*h

means

sum = sum + f(x)*h

which could be useful in computing a sum to approximate a definite integral.

Apart from the slight space-saving, this is an example of the Don’t Repeat Yourself principle, and can both improve readability and help to avoid mistakes. For example, with a more complicated expression like

A[2*i-1, 3*j+i+4] = A[2*i-1, 3*j+i+4] + f(i, j)

you might have to look carefully to check that the array reference on each side is the same, whereas that is made clear by saying

    A[2*i-1, 3*j+i+4] += f(i, j)

Also, if that weird array indexing has to be changed, say to

    A[2*i-1, 4*j+i+3] += f(i, j)

one only has to make that change in one place.

Exercise C

Write a Python function that inputs a natural number \(n\), and with the help of a for loop, computes and prints the first \(n\) Fibonacci numbers. Note that these are defined by the formulas $\( \begin{split} F_0 &= 1\\ F_1 &= 1\\ F_i &= F_{i-1} + F_{i-2} \text{ for } i \geq 2 \end{split} \)$ where I count from zero, because Python.

For now it is fine for your function to deliver its output to the screen with function print() and not use any return line; we will come back to this issue below.

Follow method 2 above, without the need for an array.

Plan before you code. Before you create any Python code, work out the mathematical, algorithmic details of this process and write down your plan in a mix of words and mathematical notation — and then check that with me before you proceed. My guideline here is that this initial written description should make sense even to someone who knows little or nothing about Python or any other programming language.

One issue in particular is how to deal with the first two values; the ones not given by the recursion formula \(F_i = F_{i-1} + F_{i-2}\). In fact, this initialization is often an important first step to deal with when designing an iterative algorithm.