{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "CNObfFIQCF1L"
},
"source": [
"# Iteration with `for`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This work is licensed under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/)\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "H07ATQX1CF1N"
},
"source": [
"## Introduction\n",
"\n",
"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.\n",
"\n",
"In Python — as in most programming languages — there are two versions:\n",
"- when the number of iterations to be done is determined before we start — done with `for` loops;\n",
"- when we must decide \"on the fly\" whether we are finished by checking some conditions as part of each repetition — done with `while` loops.\n",
"\n",
"This Unit covers the first case, of `for` loops; the more flexible `while` loops will be introduced in thssection on\n",
"[Iteration with while](iteration-with-while.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "tu8j3mKnCF1O"
},
"source": [
"\n",
"## Repeating a predetermined number of times, with `for` loops\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "kTnHXMVnCF1P"
},
"source": [
"### Example A\n",
"\n",
"We can compute the square roots of several numbers.\n",
"Here I give those numbers in a tuple (i.e., in parentheses).\n",
"They could just as well be in a list [i.e., in brackets.]"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"executionInfo": {
"elapsed": 369,
"status": "ok",
"timestamp": 1602795159862,
"user": {
"displayName": "Brenton LeMesurier",
"photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjdfjI-FuyVxn39dsea9hscchIdjExLSiyHmlnZbQ=s64",
"userId": "08187618230648844071"
},
"user_tz": 240
},
"id": "h2WzdgM9CF1Q"
},
"outputs": [],
"source": [
"import math"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 153
},
"executionInfo": {
"elapsed": 384,
"status": "ok",
"timestamp": 1602795162760,
"user": {
"displayName": "Brenton LeMesurier",
"photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjdfjI-FuyVxn39dsea9hscchIdjExLSiyHmlnZbQ=s64",
"userId": "08187618230648844071"
},
"user_tz": 240
},
"id": "beSAKgR2CF1V",
"outputId": "8f9c3654-ba2d-49a9-fd8f-d552b5ed20d7"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The square root of 1 is 1\n",
"The square root of 2 is 1.41421\n",
"The square root of 4 is 2\n",
"The square root of 9 is 3\n",
"The square root of 20 is 4.47214\n",
"The square root of 1e+06 is 1000\n",
"The square root of 3.14159e+15 is 5.60499e+07\n",
"The square root of 121 is 11\n"
]
}
],
"source": [
"for x in (1, 2, 4, 9, 20, 1000000, 3141592653589793, 121):\n",
" square_root_of_x = math.sqrt(x)\n",
" print(f'The square root of {x:g} is {square_root_of_x:g}')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "alB5ZaOECF1a"
},
"source": [
"**Aside A: Using** \"`import module`\" **instead of** \"`from module import object`\"\n",
"\n",
"Note the way that I handled importing from a module this time:\n",
"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.\n",
"\n",
"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.\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xBOak7TLCF1a"
},
"source": [
"**Aside B: Controlling the appearance of printed output**\n",
"\n",
"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.\n",
"Each `:g` appended in the `{...}` specified using the general (\"g\") format for a real number:\n",
"with this, large enough values (like 1000000) get displayed in scientific notation (with an exponent) to save space.\n",
"\n",
"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](formatted-output-and-some-text-string-manipulation.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "oj7Ow5anCF1b"
},
"source": [
"## Repeating for a range of equally spaced integers with `range()`\n",
"\n",
"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.\n",
"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!"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "ssPN2eD2CF1c"
},
"source": [
"### Example B\n",
"\n",
"Let's combine this with a previous example:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"id": "Gzp1F_sgCF1c",
"outputId": "bafda547-6c51-446b-f738-fd5a3487e696"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 is a multiple of 4\n",
"1 is odd\n",
"2 is an odd multiple of 2\n",
"3 is odd\n",
"4 is a multiple of 4\n",
"5 is odd\n",
"6 is an odd multiple of 2\n",
"7 is odd\n"
]
}
],
"source": [
"for n in range(8):\n",
" if n % 4 == 0:\n",
" print(f'{n} is a multiple of 4')\n",
" elif n % 2 == 0:\n",
" # A multiple of 2 but not of 4, or we would have stopped with the above \"match\".\n",
" print(f'{n} is an odd multiple of 2')\n",
" else:\n",
" print(f'{n} is odd')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "M2DgrV5iCF1g"
},
"source": [
"## Ranges that start elsewhere\n",
"\n",
"To specify a range of integers starting at integer $m$ instead of at zero, use\n",
"\n",
" range(m, n)\n",
"Again, the terminal value n is the first value _not_ in the range, so this gives $[m, n) = \\{i: m \\leq i < n\\}$"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "NmPKT_MjCF1g"
},
"source": [
"### Example C"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"id": "Pxs4aF2fCF1h",
"outputId": "67994d6e-b9e9-4eb5-f4c9-574bd4b2b1d9"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10 cubed is 1000\n",
"11 cubed is 1331\n",
"12 cubed is 1728\n",
"13 cubed is 2197\n",
"14 cubed is 2744\n"
]
}
],
"source": [
"for i in range(10, 15):\n",
" print(f'{i} cubed is {i**3}')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "s1fqS_z2CF1l"
},
"source": [
"**Aside C: yet more on formatting printed output**\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "GAQRlJ33CF1l"
},
"source": [
"## Ranges of equally-spaced integers\n",
"\n",
"The final, most general use of the function range is generating integers with equal spacing other than 1, by giving it three arguments:\n",
"\n",
" range(start, stop, increment)\n",
"\n",
"So to generate just even integers, specify a spacing of two:"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Ipd93wNjCF1m"
},
"source": [
"### Example D"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"id": "DYd0l00mCF1n",
"outputId": "bd3048e7-5048-4adb-a8b2-75cdf066cd68"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2^0 = 1\n",
"2^2 = 4\n",
"2^4 = 16\n",
"2^6 = 64\n",
"2^8 = 256\n"
]
}
],
"source": [
"for even in range(0, 10, 2):\n",
" print(f'2^{even} = {2**even}')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "ESJlpq1MCF1r"
},
"source": [
"\n",
"### Brief Exercise A\n",
"\n",
"Even though the first argument has the \"default\" of zero, I did not omit it here:\n",
"what would happen if I did so?"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "N4Lgo4wVCF1s"
},
"source": [
"## Decreasing sequences of integers\n",
"\n",
"We sometimes want to count down, which is done by using a negative value for the increment in function `range`."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xn5XlE79CF1s"
},
"source": [
"### Example E\n",
"\n",
"**Before** running the following code, work out what it will do — this might be a bit surprising at first."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"id": "5zfQM84aCF1t",
"outputId": "cf74c194-4f00-4952-a278-8fb529645e16"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10 seconds\n",
"9 seconds\n",
"8 seconds\n",
"7 seconds\n",
"6 seconds\n",
"5 seconds\n",
"4 seconds\n",
"3 seconds\n",
"2 seconds\n",
"1 seconds\n"
]
}
],
"source": [
"for n in range(10, 0, -1):\n",
" print(f'{n} seconds')"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "N3NgpTZDCF1x"
},
"source": [
"\n",
"### Brief Exercise B\n",
"\n",
"What is the last output, and why?"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "up1bB6fiCF1x"
},
"source": [
"### Example F: The first n factorials\n",
"\n",
"I will illustrate two methods; with and without using an array to store the values."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"id": "Db7phuZ_CF1y"
},
"outputs": [],
"source": [
"# We first need a value for n.\n",
"# It will be the input argument to the function for each method.\n",
"n = 5"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"id": "L3GQG8v1CF12",
"outputId": "a6808dad-e1d0-4273-feb0-016688dc5288"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0! = 1\n",
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n",
"The whole array is [ 1 1 2 6 24]\n"
]
}
],
"source": [
"\"\"\"\n",
"Method 1: producing a numpy array of the factorials after displaying them one at a time.\n",
"\n",
"We need to create an array of the desired length before we compute the values that go into it,\n",
"and one strategy is to create an initially empty array.\n",
"By default array elements are real numbers rather than integers,\n",
"so here see how to specify integers, with optional argument `dtype=int`)\n",
"Aside: another option is complex numbers: `dtype=complex`.\n",
"\"\"\"\n",
"\n",
"import numpy\n",
"\n",
"# Create a numpy array of n integers, values not yet specified:\n",
"factorials = numpy.empty(n, dtype=int)\n",
"\n",
"factorials[0] = 1\n",
"print(f\"0! = {factorials[0]}\")\n",
"for i in range(1,n):\n",
" factorials[i] = factorials[i-1] * i\n",
" print(f\"{i}! = {factorials[i]}\")\n",
"print(f\"The whole array is {factorials}\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Bk0_IPspCF16"
},
"source": [
"Note that if we just want to print them one at a time inside the `for` loop, we do not need the array;\n",
"we can just keep track of the most recent value:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"id": "Ix-SVpplCF17",
"outputId": "bc990111-af7b-452c-beff-7ba8feca1aa5"
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0! = 1\n",
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n"
]
}
],
"source": [
"\"\"\"\n",
"Method 2: storing just the most recent value[s] needed.\n",
"\"\"\"\n",
"i_factorial = 1\n",
"print(f\"0! = {i_factorial}\")\n",
"for i in range(1,n):\n",
" i_factorial *= i # Note: this \"*=\" notation gives a short-hand for \"i_factorial = i_factorial * i\"\n",
" print(f\"{i}! = {i_factorial}\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Zxif-rSOCF1_"
},
"source": [
"**Aside C: The shorthands `+=`, `*=`, `-=` etc.**\n",
"\n",
"In the above code, the notation\n",
"\n",
" `i_factorial *= i`\n",
"means\n",
"\n",
" `i_factorial = i_factorial * i`.\n",
"The same pattern works for many arithmetic operators, so that for example\n",
"\n",
" sum += f(x)*h\n",
"\n",
"means\n",
"\n",
" sum = sum + f(x)*h\n",
"which could be useful in computing a sum to approximate a definite integral.\n",
"\n",
"Apart from the slight space-saving, this is an example of the **Don't Repeat Yourself** principle,\n",
"and can both improve readability and help to avoid mistakes.\n",
"For example, with a more complicated expression like\n",
"\n",
" A[2*i-1, 3*j+i+4] = A[2*i-1, 3*j+i+4] + f(i, j)\n",
"\n",
"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\n",
"\n",
" A[2*i-1, 3*j+i+4] += f(i, j)\n",
"\n",
"Also, if that weird array indexing has to be changed, say to\n",
"\n",
" A[2*i-1, 4*j+i+3] += f(i, j)\n",
"\n",
"one only has to make that change in one place."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Jpb1htAhCF1_"
},
"source": [
"\n",
"#### Exercise C\n",
"\n",
"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.\n",
"Note that these are defined by the formulas\n",
"$$\n",
"\\begin{split}\n",
"F_0 &= 1\\\\\n",
"F_1 &= 1\\\\\n",
"F_i &= F_{i-1} + F_{i-2} \\text{ for } i \\geq 2\n",
"\\end{split}\n",
"$$\n",
"where I count from zero, because Python.\n",
"\n",
"*For now* it is fine for your function to deliver its output to the screen with function `print()` and not use any `return` line;\n",
"we will come back to this issue below.\n",
"\n",
"Follow method 2 above, without the need for an array.\n",
"\n",
"**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.\n",
"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.\n",
"\n",
"One issue in particular is how to deal with the first two values; the ones not given by the recursion formula\n",
"$F_i = F_{i-1} + F_{i-2}$.\n",
"In fact, this *initialization* is often an important first step to deal with when designing an iterative algorithm."
]
}
],
"metadata": {
"colab": {
"name": "05-Iteration-with-for.ipynb",
"provenance": []
},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}