- Forward


Repetition and Looping
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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
Back SMYC Forward

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
Back SMYC Forward
  • 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
Back SMYC Forward

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
Back SMYC Forward
  • It's still a pain in the @$$
  • The number of repetitions is still hard-coded
Toward a Good Approach
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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
Back SMYC Forward
  • Initialization:
    • Entering the track
  • Repeated Execution:
    • Running around the track
  • Termination:
    • Leaving the track
Important Concepts
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • Infinite Loop:
    • A loop that never terminates
    • /get
      (Courtesy of Unshelved)
      Expand
  • Indefinite Loop:
    • A loop that terminates after a number of iterations that is unknown a priori
Common Uses of Looping/Repetition
Back SMYC Forward
  • 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
Back SMYC Forward
  • Syntax: Click here for information.
    • while (boolean_expression) statement
  • Note:
    • statement can be a simple or block statement
while Loops (cont.)
Back SMYC Forward

Syntax using a Railroad/Train Analogy

railroad_while-syntax
while Loops (cont.)
Back SMYC Forward

Typical Usage using a Railroad/Train Analogy

railroad_while-typical
while Loops (cont.)
Back SMYC Forward

An Example

javaexamples/basics/WhileExample1.java (Fragment: 0)
 
while Loops (cont.)
Back SMYC Forward
  • Properties:
    • Use a pre-test
    • Use a sentinel
  • Implications:
    • May have 0 iterations
    • May be infinite
    • May be indefinite
while Loops (cont.)
Back SMYC Forward

An Example with 0 Iterations

javaexamples/basics/WhileExample1.java (Fragment: 1)
 
while Loops (cont.)
Back SMYC Forward

An Example of an Infinite while Loop

javaexamples/basics/WhileExample1.java (Fragment: 2)
 
while Loops (cont.)
Back SMYC Forward

An Example of an Indefinite while Loop

javaexamples/basics/WhileExample1.java (Fragment: 3)
 
while Loops (cont.)
Back SMYC Forward
/www
(Courtesy of Saturday Morning Breakfast Cereal)
do-while Loops
Back SMYC Forward
  • Syntax: Click here for information.
    • do statement while (boolean_expression);
  • Note:
    • statement can be a simple or block statement
do-while Loops (cont.)
Back SMYC Forward

Syntax using a Railroad/Train Analogy

railroad_do-syntax
do-while Loops (cont.)
Back SMYC Forward

Typical Usage using a Railroad/Train Analogy

railroad_do-typical
do-while Loops (cont.)
Back SMYC Forward

An Example

javaexamples/basics/DoExample1.java (Fragment: 0)
 
do-while Loops (cont.)
Back SMYC Forward
  • Properties:
    • Use a post-test
    • Use a sentinel
  • Implications:
    • Must have one iteration
    • May be infinite
    • May be indefinite
do-while Loops (cont.)
Back SMYC Forward

An Example of an Infinite do-while Loop

javaexamples/basics/DoExample1.java (Fragment: 1)
 
for Loops
Back SMYC Forward
  • Syntax: Click here for information.
    • for (initialization; boolean_expression; update) statement
  • Note:
    • statement can be a simple or block statement
for Loops (cont.)
Back SMYC Forward

Syntax using a Railroad/Train Analogy

railroad_for-syntax
for Loops (cont.)
Back SMYC Forward

An Example

javaexamples/basics/ForExample1.java (Fragment: 0)
 
for Loops (cont.)
Back SMYC Forward
  • 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.)
Back SMYC Forward
  • An Observations:
    • Arrays have a known and fixed length so are often processed using for loops
  • Example:
    • javaexamples/basics/ForExample2.java (Fragment: 0)
       
Loops and Scope
Back SMYC Forward
  • 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
      Expand
  • Why Does It Matter?
    • j can be accessed outside of the loop, i can't
      Expand
  • What About the Other Kinds of Loops?
    • The same kind of issue can arise though it is less common
Loops and Updating
Back SMYC Forward
  • 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
Back SMYC Forward
  • 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)?
There's Always More to Learn
Back -