Iteration with for
Contents
6. Iteration with for
#
Estimated time to complete: one hour.
6.1. 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 section covers the first case, of for
loops; the more flexible while
loops will be introduced in Iteration with while.
6.2. 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: Using “import module
” instead of “from 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 Some Text String Manipulation.
6.3. 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
6.4. 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.
6.5. 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?
6.6. 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
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.