Nested Loops

Nested Loops
A Programming Pattern

Computer Science Department

bernstdh@jmu.edu

Nested Loops

An Observation:
- The statement (or block statement) that constitutes the body of the loop can contain a loop
Terminology:
- Such loops are said to be "nested"

Common Uses of Nested Loops

Creating:
- Prompting for valid input within another loop (this is not normally thought of as nested loops)
- To create a "table"
Calculating:
- To search for a value in a "table"
- "Generate and Test" algorithms (i.e., generate candidates and see if they satisfy a condition)

Creating a Table

An Example

javaexamples/programmingpatterns/AdditionTableExample.java (Fragment: 0)

Generate and Test Algorithms

An Example

javaexamples/programmingpatterns/PrimeSearcher.java

Number of Iterations

Casual Analyses:
- In many cases, the total number of iterations is the number of "inner iterations" times the number of "outer iterations"
- Sometimes one loop depends on the other
Formal Analyses:
- Involve finding bounds on the worst case

Number of Iterations (cont.)

A Simple Example

javaexamples/programmingpatterns/AdditionTableExample.java (Fragment: 0)

Number of Iterations (cont.)

An Example in which the Inner Loop Depends on the Outer Loop

javaexamples/programmingpatterns/AdditionTableExample.java (Fragment: 1)

Writing Nested Loops

A Common Strategy:
- Divide the problem into pieces
Applied to Nested Loops:
1. Write the outer loop (ignoring the details of the inner loop)
2. Write the inner loop

There's Always More to Learn