Introduction to Iteration

15. Introduction to Iteration

Key Concepts

Iteration
for loop (a counting loop)
while loop
loop equivalence

Introduction

There are many scenarios in our life where we repeat some actions for a period of time. Let's list some of them:

While there are still donuts in the box, eat one.
Send each relative that sent you money for your birthday a thank-you note.
Drive until you see a fork in the road.
Put each item of clothing on the floor in the laundry basket.
Give a cookie to each of your instructors.
Bake the roast until it has an internal temperature of 220 degrees.
Lather, rinse, repeat. (Buggy!)

In this lesson, we'll learn how to express algorithms like these in Java.

The for loop

Imagine that you're on contract to the weather station, and they want you to collect temperature statistics. In particular, they'd like you to find the average high temperature over a period of time. You already (sort of) know how to do this:

int totalTemp = 0;

int mondayHi = input.readInt("Monday's high temp?");
totalTemp = totalTemp + mondayHi;
int tuesdayHi = input.readInt("Tuesday's high temp?");
totalTemp = totalTemp + tuesdayHi;
int wednesdayHi = input.readInt("Wednesday's high temp?");
totalTemp = totalTemp + wednesdayHi;
  ...
int averageHi = totalTemp / 7;

This approach has some serious drawbacks. What are they? What we really want to say is something like:

For each day of the month (week or whatever period) get the high
temperature and accumulate it.  Afterwards, divide the total
temperature by the number of days in the period.

Java lets us express this algorithm almost verbatim:

int totalTemp = 0;
int numDays = 30;

for (int i=0; i < numDays; i=i+1) {
  int todaysHi = input.readInt("High temperature for day " + i);
  totalTemp = totalTemp + todaysHi;
}
int averageHi = totalTemp / numDays;

The for-loop in Java has the following pattern:

for (<initializer-statement>; <condition-expression>; <update-statement>) {
  <body>
}

The semantics is as follows: First, the

initializer
  statement

is executed. Then, while the condition-expression is true, the body statements, followed by the update-statement is executed.

Since so many for-loops contain statements like i=i+1 in their update step (indeed, incrementing by one is very common in other places too) you'll see the following shorthand used frequently:

i++;    // means i=i+1

The while loop

Now let's say we want to find the average rainfall over a period of consecutive days with rain. We might express the algorithm for doing this as follows:

While there is rain on a given day, accumulate the total rainfall.
Afterwards, calculate the average.

This problem is not naturally counting loop -- it loops simply until some condition is true. Java supports this kind of loop too:

int todaysRainfall = input.readInt("Today's rainfall?");
int daysWithRain = 0;

while (todaysRainfall > 0) {
  daysWithRain = daysWithRain + 1;
  totalRainfall = totalRainfall + todaysRainfall;
  todaysRainfall = input.readInt("Today's rainfall?");
}
int averageRainfall = totalRainFall / daysWithRain;

We can express this as a for loop, but it's not naturally a counting loop. It is worth convincing yourself, though, that every while loop can be expressed as a for loop, and vice-versa. For example, we could transform the above into a for loop:

int daysWithRain = 0;
for (int todaysRainfall = input.readInt("Today's rainfall?");
     todaysRainFall > 0; 
     todaysRainfall = input.readInt("Today's rainfall?")) {
  daysWithRain = daysWithRain + 1;
  totalRainfall = totalRainfall + todaysRainfall;
}
int averageRainfall = totalRainFall / daysWithRain;

In general, it's better style to use a for loop when the loop is naturally described as a counting loop -- a loop that iterates over a sequence or range of numeric values.