Repetition and Looping

Repetition and Looping
An Introduction with Examples in Java

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

Algorithms often need to repeat a step or a sequence of steps
- Example: Check all batting averages to find the player with the highest
We often want to apply the same algorithm multiple times
- Example: Convert multiple speeds in knots to the equivalent speeds in mi/hr (e.g., to create a table)

The Natural Approach to Repetition

An Example

feetPerKnot = 6080.0;
feetPerMile = 5280.0;

speedInKnots = 1.0;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

speedInKnots = 2.0;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

speedInKnots = 3.0;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

speedInKnots = 4.0;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

// ...

Shortcomings of this Approach

It's a pain in the @$$
It is easy to make a mistake (e.g., omit/repeat a speed)
The number of repetitions is hard-coded

A Slightly Better Approach to Repetition

At Least We Can Cut and Paste (and Avoid Some Mistakes)

feetPerKnot  = 6080.0;
feetPerMile  = 5280.0;
speedInKnots = 0.0

++speedInKnots;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

++speedInKnots;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

++speedInKnots;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

++speedInKnots;
speedInMPH  = speedInKnots * feetPerKnot / feetPerMile;
JMUConsole.printf("%5.2f\n", speedInMPH);

// ...

Shortcomings of this Approach

It's still a pain in the @$$
The number of repetitions is still hard-coded

Toward a Good Approach

Some Commonalities:
- We start by initializing a variable that gets used in one or more calculations
- We perform the calculation
- We update the variable that gets used in the calculation
- We determine if we're done
What We Would Like:
- Statements that allow us to do this easily

Definitions

Loop:
- A portion of a program that repeats a statement or group of statements
Body of a Loop:
- The statement or group of statements that is repeated
Iteration:
- One "pass" through the body of a loop

An Analogous Situation

Initialization:
- Entering the track
Repeated Execution:
- Running around the track
Termination:
- Leaving the track

Important Concepts

Termination/Exit Condition:
- Can involve a pre-test (i.e., a test at the top) or a post-test (i.e., a test at the bottom)
Sentinel:
- A value that would normally be "invalid" that is used to signal that a loop should terminate

Important Concepts (cont.)

Infinite Loop:
- A loop that never terminates
- (Courtesy of Unshelved)
Indefinite Loop:
- A loop that terminates after a number of iterations that is unknown a priori

Common Uses of Looping/Repetition

Creation:
- Prompt a user for multiple values
- Read multiple values from a file
- Repeatedly prompt for a single valid input (e.g., when the user might make mistakes)
Calculation:
- Perform the same operation on a collection/array of values
- Sort a collection/array of values
- Move through "time" or "space" (e.g., in a simulation or game)
- Searching through a set of possible values (e.g., to find the zero of a function)

while Loops

Syntax:
- while (boolean_expression) statement
Note:
- statement can be a simple or block statement

while Loops (cont.)

Syntax using a Railroad/Train Analogy

while Loops (cont.)

Typical Usage using a Railroad/Train Analogy

while Loops (cont.)

An Example

javaexamples/basics/WhileExample1.java

(Fragment: 0)

        speedInKnots = 1.;

        while (speedInKnots < 50.) 
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;
            
            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);
            
            speedInKnots = speedInKnots + 1.;
        }

while Loops (cont.)

Properties:
- Use a pre-test
- Use a sentinel
Implications:
- May have 0 iterations
- May be infinite
- May be indefinite

while Loops (cont.)

An Example with 0 Iterations

javaexamples/basics/WhileExample1.java

(Fragment: 1)

        //    A while loop with 0 iterations
        speedInKnots = 51.;

        while (speedInKnots < 50.) 
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;
            
            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);
            
            speedInKnots = speedInKnots + 1.;
        }

while Loops (cont.)

An Example of an Infinite while Loop

javaexamples/basics/WhileExample1.java

(Fragment: 2)

        speedInKnots = 1.;

        while (speedInKnots > 0.) 
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;
            
            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);
            
            speedInKnots = speedInKnots + 1.;
        }

while Loops (cont.)

An Example of an Indefinite while Loop

javaexamples/basics/WhileExample1.java

(Fragment: 3)

        // Prompt the user and assign the response to speedInKnots

        while (speedInKnots > 0.) 
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;
            
            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);
            
            // Prompt the user and assign the response to speedInKnots
        }

while Loops (cont.)

http://www.smbc-comics.com/comics/20120628.gif

(Courtesy of Saturday Morning Breakfast Cereal)

do-while Loops

Syntax:
- do statement while (boolean_expression);
Note:
- statement can be a simple or block statement

do-while Loops (cont.)

Syntax using a Railroad/Train Analogy

do-while Loops (cont.)

Typical Usage using a Railroad/Train Analogy

do-while Loops (cont.)

An Example

javaexamples/basics/DoExample1.java

(Fragment: 0)

        speedInKnots = 1.;

        do
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;

            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);

            speedInKnots = speedInKnots + 1.;
        } 
        while (speedInKnots < 50.);

do-while Loops (cont.)

Properties:
- Use a post-test
- Use a sentinel
Implications:
- Must have one iteration
- May be infinite
- May be indefinite

do-while Loops (cont.)

An Example of an Infinite do-while Loop

javaexamples/basics/DoExample1.java

(Fragment: 1)

        speedInKnots = 1.;

        do
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;

            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);

            speedInKnots = speedInKnots + 1.;
        } 
        while (speedInKnots > 0.);

for Loops

Syntax:
- for (initialization; boolean_expression; update) statement
Note:
- statement can be a simple or block statement

for Loops (cont.)

Syntax using a Railroad/Train Analogy

for Loops (cont.)

An Example

javaexamples/basics/ForExample1.java

(Fragment: 0)

        //    A simple for loop

        for (speedInKnots=0.; speedInKnots < 50.; speedInKnots=speedInKnots+1.)
        {
            feetPerHour = speedInKnots * feetPerKnot;
            speedInMPH  = feetPerHour / feetPerMile;

            JMUConsole.printf("knots: %5.2f\tmph: %5.2f\n", 
                              speedInKnots, speedInMPH);
        }

for Loops (cont.)

Properties:
- Use a pre-test
- Use a "built-in" initialization
- Use a "built-in" sentinel
Implications:
- May have 0 iterations
- May be infinite
- Are most frequently definite (i.e., not indefinite)

for Loops (cont.)

An Observations:
- Arrays have a known and fixed length so are often processed using for loops

Example:

javaexamples/basics/ForExample2.java

(Fragment: 0)

       n = Array.getLength(args);       
       for (int i=0; i<n; i++)
       {
           JMUConsole.printf("Argument %d: %s\n", i , args[i]);
       }

Loops and Scope

Consider These Examples:
- for (j=0; j<50; ++j)
- for (int i=0; i<50; ++i)
What's Different?
- The scope of i and j
Why Does It Matter?
- j can be accessed outside of the loop, i can't
What About the Other Kinds of Loops?
- The same kind of issue can arise though it is less common

Loops and Updating

An Observation:
- The update pattern is commonly used in loops
Which Approaches?
- Explicit updates (e.g., age = age + 1;)
- Compound assignment operators (e.g., age += 1;)

Using Loops in Your Programs

Admitting you have a Problem:
- Look for repeated uses of the same statements/operations/algorithm (i.e., duplication)
Choosing Between a Loop and a Function/Method:
- Functions/methods are appropriate when the same statements/operations/algorithm are used in different places
- Loops are appropriate when the same statements/operations/algorithm appear in one places (e.g., one right after another)
Constructing the Loop:
- Carefully identify the repeated/duplicate statements/operations/algorithm
- Look for the (limited number of) variables that change in the repetitions
- Identify the way in which those variables change and their initial values
- Identify the termination condition(s)
Choosing a Loop:
- Is the loop definite (prefer for) or indefinite (prefer while or do-while)?
- Must the loop have at least one iteration (prefer do-while)?