Unit 5: Iteration with Loops

5.0. Overview

There are two abilities we need to be able to write programs, and those are handled by two corresponding control structures that we need to write our programs. We need the ability to branch (handled by if-else conditionals), and the ability to iterate (handled by while and for loops).

Up this point we've dealt with two things that have each had their own challenges. The first challenge was developing an understanding of boolean statements: the if statement, the if-else statement, and variations on these, including a switch-style series of alternatives, and nested if-else statements that allow us to drill down through multiple options.

The second challenge was navigating "object-oriented design", and learning to write programs that implemented classes, methods, and testers.

In this unit, we turn our attention to loops. Computers specialize in repetitive operations which can be repeated very quickly, so understanding how to write loops—and how to write loops well—is at the very heart of programming.

Let's get started.

1. while loops, do loops, Debugging
2. for loops
3. Sentinel Values, Common Loop Algorithms
4. Nested Loops
5. Random Numbers, Simulations

5.1. Overview: while loops, do loops, Debugging

There are two major types of techniques for repeating, or iterating, sections of code. The first, and the most powerful, is the while loop.

5.1.1. Intro to Iteration

The if statement has to do with making decisions, and it's the first kind of control structure that we have in Java to alter the flow of our instructions.

The second kind of control structure we're going to have in our toolbox is the loop, which allows us to make our computers repeat sequences of code, many many times, very very fast. Once we have our branching and our looping control structures in place, we are going to be able to write some amazing code!

5.1.2. The while loop

There are basically three types of loops that we're going to work with in Java, although technically, any programming language only needs one. The most fundamental type of loop—the most powerful, the most versatile—is the while loop.

The while-loop is sometimes called a conditional loop—it continues to repeat as long as a condition evaluates as true.

Here's another example of a conditional loop.

5.1.3. Off-by-One Errors

There are a number of important aspects to programming a loop that we have control over. In the example below, for example, we design the loop based on:

• the initial value of i? (0, or 1?)
• the comparison operator (<, or <=?)
• the final value (10000? 10001?)
• the order of the statements in the loop (do I print i first and then increment, or do I increment first and then print?)

These factors all affect the loop's operation.

Off-by-one errors typically happen during the first iteration or the last iteration of the loop, so it's important to check the status of variables at those times especially carefully. If you do find that there's a problem with the loop, you're strongly discouraged from just randomly altering your loop parameters. A program that doesn't behave as expected reveals that you don't perfectly understand how it works—better to make the effort to analyze it and make a repair that you understand rather than just changing something and "seeing what happens."

5.1.4. The Investment class

Continuing with out interest in things financial, take a moment to make sure you understand the Investment class here.

Identify the instance variables, the constructors, the accessor methods, and the mutator methods. Run through the class by hand to make sure you understand how the program works.

5.1.5. Using a Debugger

Three things you need to know when using a debugger.

A better strategy, if you're using an IDE, is to use the included Debugger. Here's the basic process, in 3 steps.

1. Set a breakpoint
   In BlueJ, click on the line number of a statement so that a Stop appears at that location. Your program will run normally until you hit that breakpoint, and you can Inspect the state of various variables at that point. When you're ready to continue, click Continue.
   In a complex program, you may wish to set multiple breakpoints to inspect what's happening at various parts of your program.
2. Step
   If you've hit a breakpoint, rather than hitting Continue you can choose to Step through various instructions. This has the effect of executing the instructions in that call/module one at a time, so you can see what's happening to your variables as you go.
   But what if those instructions include method calls?
3. Step into
   Click on Step into to descend into a method call to see what's happening there.

5.1.6. Debugging Strategy

You don't want to use a debugger all the time, every time, to go through a program. That takes too much time. But if you're stuck and can't figure something out, the debugger allows you to follow the flow of your program and quickly find problems.

The best strategy is to set a breakpoint just before where you think your program is blowing up. Run the program, and then Step through statements until you see the failure. Then do it all again, but Step Into the method that you think might be causing you problems. This "divide-and-conquer" strategy should help you nail down your problem pretty quickly.

5.1.7. do loops

A standard while loop checks the condition before doing something, but sometimes you want to do something first, and then check some boolean condition.

Example: Get a user's input and then see if it's valid. The loop below will continue asking a user's age until he/she enters an age that is a positive value.

The do loop can be useful and logical to use in certain situations, but most people seem to prefer writing a standard while loop with a structure that is equivalent to the do loop's operation.

5.2. Overview - for loops

Although a conditional loop like the while loop is all that is necessary to write programs, we often need a loop that will count through some series of values. The for loop is another type of loop that is very handy for creating unconditional loops that iterate a value over some known range of values.

5.2.1. The for loop

As we've said, the while loop is sufficient for any looping needs you might have, but there's one type of while loop that is so common, most languages have an additional structure for it: the for loop. If you need to count up or down from some value, to a terminal value, a for loop is what you should probably use.

We've already seen how you can count with a while loop:

Here's how you'd do the same thing with a for loop:

Note that if the counting variable i has already been declared, you don't have to declare it in the body of the loop.

For really big integers, you'll need to investigate the slow but powerful BigInteger class.

Just as with while loops, you'll need to be careful to avoid off-by-one errors when writing your for loops!

5.2.2. Using loops for different objectives

Up to this point, we've played a bit with the two main types of loops in Java: the while loop, and the for loop.

5.3. Overview - Sentinel Values, Common Loop Algorithms

We've discussed while loops and for loops, and seen a few simple examples of how they might be used. Let's take a look at some of the ways that loops are commonly used.

5.3.1. Sentinel values

A sentinel keeps watch, and sentinel values are values that are watched for in a loop to find out when the loop should complete.

5.3.2. The break and continue statements

The idea of checking values in the middle of the loop in the "loop-and-a-half" structure above strikes some people as inelegant, and not the cleanest way to code these situations.

One useful alternative involves a break statement in the middle of the loop:

Our textbook doesn't use break statements this way, but it's a very common strategy for lots of coders, and allowed by Java.

5.3.3. Common Loop Algorithms

As you might expect, loops are used for a lot of different "standard tasks" in program. Here are some of the most common.

5.3.3.1. Keeping a Running Total of Values

We often need to sum up a series of values. A variable called sum here does just that:

5.3.3.2. Counting Matching Data

Sometimes we need to identify which items in a sequence match a certain requirement—counting vowels, for example:

5.3.3.3. Data Validation / Error-Trapping

Sometimes we need to validate data that the user has entered, or make sure that the user hasn't entered data that will cause our program to crash.

5.3.3.4. Finding the Maximum or Minimum in a Series of Values

Being able to find the largest or smallest value in a series turns out to be enormously useful.

5.3.4. Sequential Data Analysis

Take a look at this DataSet class that calculates information about a set of values entered by the user.

Analyzing the code, we can see how it works. Let's see how a runner program might interact with this class, getting input from the user via a Scanner, and using a sentinel value to manage that interaction:

5.3.5. Finding primes

5.4. Overview - Nested Loops

We've had a good chance to look at how we can use loops to quickly work through a series of values.

Often we'll need to use a looping structure as the body of a larger, outer loop. Such loops are said to be nested.

5.4.1. Nested loops

Just as we can nest if-else statements inside other if-else statements to work on multiple levels of a problem, we can nest loops inside other loops.

Pseudocode example: Going through a document word by word

Pseudocode example: finding the total assets of a bank

5.4.2. Nested counting loops

One very common type of loop pattern involves using two loops to work through a 2-dimensional grid or table.

Generally:

5.5. Overview - Random numbers, Simulations

We've had a good chance to look at how we can use the two types of loops—conditional (while loops) and unconditional (for loops).

Now let's look at a new type of program that will make good use of what we've learned: models, or simulations.

5.5.1. Random Numbers and Simulators

5.5.2. Getting Random Integers

To get pseudo-random numbers in a Java program, there are two common strategies.

5.5.2.1. The Math.random() method

In many simulations we need to create an integer value within some range of values: 1-6 for a dice roll, for example. We can return any desired range of values by manipulating the result returned by Math.random():

What's going on here?

1. Math.random() creates a random double between 0 and 0.9999999999999999.
2. That value is multiplied by 6 to yield a double number between 0 and 5.999999999999994.
3. We add 1 to that value to get a double number between 1 and 6.999999999999994.
4. We cast that value as an int to get an integer between 1 and 6 that is stored in the int variable dieRoll.

This strategy for creating integers within a given range is very common.

5.5.2.2. The Random package

The Random package contains a more extensive collection of utilities that allow you to work with random and pseudorandom values. Use of that package is not required for this class, although you'll see it used in examples in our textbook, so it helps to know how to create a Random object.

5.5.3. Writing a simulation