Chapter 16 - For-loop examples

1.1 Using an accumulator

We have seen a number of examples using a for-loop to repeat an action some given number of times. We have also seen in these examples that the loop variable takes on each value in the given range expression, and we can use that variable within the repeated statements (the “body” of the loop). In addition we have seen that we can use a for-loop to iterate over any list, not just a range of numbers.

In this section we want to extend these ideas to solve some kinds of problems that require updating some additional variable or variables within a loop. Such a variable is called an accumulator or counter, depending how it is being used.

Recall this code that prints the five numbers 1 through 5:

What if instead we want to add up those 5 numbers? Well, instead of printing each number, we want to add it to a total that we can print at the end. Before we add any numbers at all, the total is zero, so we initialize it to zero before starting the loop.

This would work exactly the same way for any list of numbers. Recall that in Python, we can create a list of literal values just by putting them in square brackets, separated by commas.

The variable total is often referred to as an accumulator because it “accumulates” the values produced by the iterations of the loop.

1.1.1 The increment operator +=

Take another look at the statement:

total = total + num

We’re taking the variable total, adding a value to it, and then storing the result back in the variable total. This kind of thing happens so often that there is a shorthand notation for it. The statement above could be written as

total += num

You could think of this as saying “increment total by the value num”.

1.2 Using a counter

One of our previous examples was to use a range to print all the verses to the song “99 bottles”. We had to construct a range that would provide the values from 99 down to 1 in steps of -1.

Another way to think about it that can be much more flexible is to use an auxiliary variable to keep track of how many bottles there are. It starts at 99, and we subtract 1 each time, and do it 99 times:

As with adding to a total, the update step bottles = bottles - 1 can be written with a similar shorthand, bottles -= 1.

The variable bottles in the previous example would be called a “counter” - it’s just counting the number of bottles left. This is not a very interesting example, because we know in advance it’s just going to count down from 99 to 0, which is why we can just as well use a range expression. Usually things are not so simple.

For example, can we write a function that, given a list, determines how many numbers in it are even? For example, if we have the list

my_list = [5, 3, 2, 2, 14, 15, 6]

the answer is 4. How do we know? We look at each element of the list in turn, and add 1 to our mental tally if the number is even. In pseudocode, we’re doing this:

for each number in the list
    if it's even
        add 1 to the total

To turn this into real code, we have to remember that the total has to be initialized before the loop. To decide how it should be initialized, we ask ourselves: what would be the correct answer if there are no even numbers in the list? That tells us we should initialize the total to zero before the loop starts.

1.3 Tracing execution

Suppose we want to write a loop that “finds” something in a list. For instance, you’re given a list and you want to check whether or not it includes the number 42. In general we could write this as a function with two parameters, the list itself, and the “target” value you want to search for. We might try to write it like this, where, for each value in the list, we check whether it is equal to the target.

We try it out on a sample list. Since 20 really is in the list, we should get an answer of True. But the result comes out False. What’s wrong? To track down the problem, we’ll illustrate a technique for “tracing” through a list. We draw a little table with a column for each variable and a line for each iteration of the loop. Each line is like a memory map that we fill in with the values of the variables at the end of the loop body.

Since the variable “target” never changes, we don’t need a column it. In this case, we already know there will be four iterations.

Variables: x answer

We read the loop body and fill in the table with the value of each variable when the loop body finishes executing.

_static/find_target.png

In the first iteration, x is 10. Since 10 isn’t equal to the target value 20, the answer will be set to False.

Variables: x answer
First iteration 10 False

Now, the loop body executes again with x holding the next value in the list, in this case 20. Since 20 is equal to the target, answer is set to True.

Variables: x answer
First iteration 10 False
Second iteration 20 True

So far so good. But now the loop body executes again with x equal to 30. 30 isn’t equal to 20, so answer is set to False again.

Variables: x answer
First iteration 10 False
Second iteration 20 True
Third iteration 30 False

The same thing happens in the last iteration when x is 40.

Variables: x answer
First iteration 10 False
Second iteration 20 True
Fourth iteration 40 False

Execution of the loop is now complete, and the value returned the variable “answer”, which is False. That’s not what we wanted!

We need to be sure to set the answer to True if we find the target value, but to leave it alone otherwise. If we never find the target, we want the answer to be False, so we’ll start out with that value. The logic should look like this:

answer = False
for each number in the list
    if the number is equal to the target value
        answer = True
return answer

And the Python code looks just like that:

1.3.1 Multiple return statements

There is another thing to notice about the example above. Imagine you have a very long list and the target value occurs near the beginning. Suppose you have a list of a million elements and you’re looking for the number 42, and it happens to be the 10th element. Do you really need to keep looking at the other 999, 990 elements in the list? Not really, because once you find the element 42, you know you’re going to return True from the function. You might as well just end the search then and there.

This is a case in which it makes sense to use multiple return statements. We can put a return statement inside the loop to return the value True as soon as we find the target.

1.4 More on accumulators

An accumulator does not always have to work with addition. For example, the “factorial” of a number n is obtained by multiplying together all the numbers from 1 through n. Let’s try the very first example again, using multiplication instead of addition. If we multiply 1 * 2 * 3 * 4 * 5, the answer should be 120.

Why are we getting an answer of zero? The problem is in the initialization of result. When we are adding, it makes sense to start with zero. If we don’t add any numbers at all, the answer should be 0. For multiplication, we have to start with 1.

We can iterate over the individual characters of a given string with a for-loop, just like we can a list:

We can use the accumulator pattern with string concatenation. For example, we could make a string of 5 “-” characters like this:

Notice that we start with an empty string and add on a new character each iteration.

So let’s say we want to take a string, say “Steve” and convert it to a string such as “-S-t-e-v-e-”. For each character in the string, we want to append a “-” to the result, and then append the character itself. Finally we should add a “-” at the end.

As another example, we can use a similar strategy to create a string with all the characters reversed:

1.4.1 String “multiplication” in Python

As an aside, note that a Python programmer would not write a loop to create a string with 5 dashes. It can just be written with the expression '-' * 5, meaning “concatenate the ‘-‘ character five times”.