Iteration

0. Learning objectives

1. Loops

We discussed how we can write and call functions to perform calculations that are abstracted in terms of some input variables (parameters). We have also looked at how you can use conditionals to make choices within your code in order to follow different computational paths. Nonetheless, even with functions and conditionals, our code is still missing the ability to do something that is fundamental to automation: repeating code! We can explicitly repeat code using loops.

There are two types of loops we will see: for loops and while loops. Note that you can always convert a for loop into a while loop. At a very low abstraction level (machine code) they are both implemented in using identical constructs, however, it may be easier for us humans to use one over the other depending on the specific application.

On top of for and while, we will also see a few new keywords in Python: the break and continue keywords.

1.0. for loops

If you wanted to count how many vowels are in a string, what would you do? You might come up with an algorithm that involves looking at each character, determining whether or not it is a vowel, and then adding up the number of vowels that you see. Using a loop, we can do exactly that by going through one chracter after the other using their indices!

What we need to do this, is an easy way to iterate through these indices, what we call an iterable.

Strings, as sequences (or collection) of characters are, in fact, iterable. This is also one of the reasons why we are able to use the in operator on a string to find out if a character (or substring) is present inside the string. You can almost see the interpreter going through one character at a time in the string and check.

We can actually leverage this behavior of the in operator to loop through every item in an iterable (a sequence). For example, in the case of a string, we can use it to loop through every character. But, what is a loop?

A loop is a programming language construct that allow us to go through an iterable. Feels like we are going in circle, doesn't it? Let's look at a specific construct.

The for loop, see the template on the right, introduces a new keyword: the for keyword. This is followed by a variable, the in keyword, an iterable we want to go through, a colon (:) - to tell Python that a block of code we want to repeat for each item inside the iterable is coming - and finally the block of code indented relative to the for keyword.

At each iteration, every item in the sequence will get in turn assigned to the variable. Therefore, we can use the value stored in variable (which, again, changes on every iteration) if we need to.

So far, we iterated through the characters in a string. But what if we want to iterate through a sequence of numbers? Like, maybe iterate through the numbers 0 to 10?

We can use the range(start, end, step) function. This function creates an iterable sequence starting at start, ending at end in steps of step. The way range() works is just like what we saw with string slicing! You can think it as a function that generates the indexes that your slicing operator, with the same parameters, would generate. You can even use negative steps or omit some of the parameters, as we will see. For example, range(10) will create an iterable sequence with the numbers 0 to 9 (remember it goes up to but not including 10).

Example 0: Playing with for loops

Here are a couple of simple examples.

Example 1: Counting vowels with a loop

Let's now write our vowel counter in two different ways. In the first way, we will iterate through each character. In the second way, we will iterate through the indices 0 to the number of characters - 1 in text. In the index example, notice how we are accessing text[i] since i holds the current integer value generated using the range() function.

Example 1: Arithmetic series

In 1780s, Carl Friedrich Gauss's teacher (wanting to quiet down the class) gave the class a seemingly impossible task: add up all the numbers from 1 to 100. This should have kept them busy for hours. However, Gauss finished the problem almost immediately! In fact, Gauss proved that the sum of the first $n$ natural numbers (i.e. the sum of the numbers starting at $1$ and going until $n$) is equal to $n(n+1)/2$.

Here is a possible iterative solution to the problem.

Challenge 0: Adding even numbers

Try writing your own function that adds all of the even integers between $1$ and $n$. Challenge yourself to write the function in two ways: one using a conditional and one using the step parameter of the range function. The more practice you get, the better!

1.1. while loops

for loops are probably one of the most common techniques for iterating through a sequence. But it requires that you have a sequence to iterate through or, at least, to "know" how many iterations you need to accomplish. What if you don't know (beforehand) the number of iterations that you have to perform? For example, coming back to the cereal example we looked at when discussing algorithms: you should continue eating cereal while there is cereal left in your bowl (or until you're not hungry anymore, whichever comes first). I don't think anyone eats cereal knowing they will take 23 spoonfuls. Instead, you want to keep iterating as long as (while) some condition is true.

This is where the while loop construct can be useful. It does exactly what it sounds like: it keeps executing a block of code while some condition is True. For a template of how this is written in Python, please see the example on the right. The condition is any expression that evaluates to either True or False. Note that within your block of code, something needs to happen so that the condition eventually evaluate to False, otherwise the loop while run forever!

Example 0: Playing with while loops

Here are a couple of example of loops coded using the while construct. Some of them are examples that we have done above using the for construct. Can you identify them? They both solve the same problem. In what do they differ?

Example 1: Doubling an investment

Let's see a good use of a while loop. We will use an application from finance and try to find the number of years until an investment doubles. We will assume that we start off with some amount of money (principal) $P$ and we are investing in a fund that will give us an interest $r$ every year. That interest is then going to be added to our principal and the new interest, at the end of the following year, will be calculated on this sum, and so on, year after year. This is known as compounding. In other words, after year 1 we will have $P(1+r)$ dollars, after year 2 we will have $P(1+r)(1+r)=P(1+r)^2$ dollars, meaning that after $n$ years we will have $P(1+r)^n$. Yes, we could carry out this calculation analytically, but try to do it with a while loop.

Have a look at first solution and notice that the condition for the while in our problem is current_value < 2 * P. Remember that the comparison operator < will return either True or False depending on the result of the comparison. This is equivalent to write (current_value < 2*P) == True. In the second solution we use a technique that is often used for more complex problems. We define a flag variable which is a Boolean, check the value of that variable in our while condition, and then update the variable if certain conditions are met. In this case if the value of out investment has doubled. This is often used if there are multiple condition that can stop the loop and are spread around our code block.

Challenge 0: For loops to while loops (and vice-versa)

Try re-writing some of the functions that we have seen using for loops with while loops (vowels, add_up_to) and some of the functions that we have seen using while loops with for loops (factorial, find).

Challenge 1: When while loops are more appropriate

I did not ask you to write the function investment_double using a for loop. Why might this function be more difficult to write using a for loop?

The exact number of iterations is not known until we have completed the loop, because it is dependent on current_value. In fact, the purpose of our loop is to compute years, which is the number of times we run the body of the loop!

1.2. break and continue

Sometimes you might want to skip an iteration, or something happened inside your loop that makes you want to abandon either the current or any further iteration. For example, what if you want to perform a certain computation on all the number up to n (let's say you want to double them) but you want to skip that computation for all the multiples of 5? Luckily we have a special keyword to skip iterations: the continue keyword. If Python hits the continue keyword, it will skip the remaining lines of code in the block for the current iteration and go right to the next iteration in your loop. Here is an simple example:

Another useful keyword is the break keyword. If Python reaches a break, then it will abandon not only the current iteration, but the entire loop, all future iterations, and jump to the end of the loop (back to the original indentation). This keyword might be useful if you don't know when to exit the iteration. Maybe you are interacting with a human and you don't know when they are going to be done entering data or typing on a keyboard. Consider the following example where we wrote code simulating a 'dumb terminal' (they were e real thing, look them up) where you can continue to type lines and get the "I don't understand!" reply until you type a line with only the word 'exit' in it at which point the terminal with just quit. In this case, break would work very nice since it can exit your loop.

break and continue should be used only when absolutely necessary since they make the code harder to read and understand. When people see a while or for, they will expect the loops to run until completion and consider the code as a block that does something so many times under the condition specified at the beginning of your loop. If you use break or continue, you throw a wrench in this usual interpretation. So, if you have to use it, make sure you clearly comment your code specifying its behavior.