4.4 Nested Iteration

Introduction

Nested iteration occurs when one loop is placed inside the body of another loop. This powerful programming technique allows us to work with multi-dimensional data, create complex patterns, and solve problems that require examining combinations of elements. Understanding nested loops is essential for handling tasks ranging from processing two-dimensional arrays to generating multiplication tables. This guide explores how nested loops work and provides practical examples of their applications.

Understanding Nested Loops

In nested iteration, we have:

• An outer loop that controls the overall number of iterations
• An inner loop that executes completely for each iteration of the outer loop

This creates a multiplicative effect: if the outer loop runs 5 times and the inner loop runs 3 times for each outer iteration, the inner loop body will execute a total of 15 times.

Types of Nested Loops

Various loop types can be nested in different combinations:

• For loop inside another for loop
• While loop inside a for loop
• For loop inside a while loop
• While loop inside another while loop

The most common pattern is nesting for loops, especially when working with data where the number of iterations is known in advance.

Execution Flow in Nested Loops

Understanding how nested loops execute is crucial:

1. The outer loop executes its initialization step
2. The outer loop's condition is checked
3. If true, the outer loop's body begins executing
4. The inner loop executes completely (all its iterations)
5. After the inner loop finishes, the outer loop's increment step runs
6. Steps 2-5 repeat until the outer loop's condition becomes false

This diagram illustrates the execution flow:

┌───────────────────┐
│ Outer Loop Starts │
└─────────┬─────────┘
          │
          ▼
┌───────────────────┐     false
│   Outer Loop      │──────────► (Exit Both Loops)
│   Condition?      │
└─────────┬─────────┘
          │ true
          ▼
┌───────────────────┐
│ Inner Loop Starts │
└─────────┬─────────┘
          │
          ▼
┌───────────────────┐     false
│   Inner Loop      │──────────┐
│   Condition?      │          │
└─────────┬─────────┘          │
          │ true               │
          ▼                    │
┌───────────────────┐          │
│ Execute Inner     │          │
│ Loop Body         │          │
└─────────┬─────────┘          │
          │                    │
          ▼                    │
┌───────────────────┐          │
│ Inner Loop        │          │
│ Increment         │          │
└─────────┬─────────┘          │
          │                    │
          └────────────────────┘
                   │
                   ▼
┌───────────────────┐
│ Outer Loop        │
│ Increment         │
└─────────┬─────────┘
          │
          └────────► (Return to Outer Loop Condition)

Basic Example of Nested For Loops

Here's a simple example using System.out.println and System.out.print to display a pattern:

// Print a 5x5 grid of asterisks
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        System.out.print("* ");  // print without line break
    }
    System.out.println();  // add line break after inner loop completes
}

Output:

* * * * * 
* * * * * 
* * * * * 
* * * * * 
* * * * * 

Note how:

• System.out.print() outputs text without moving to the next line
• System.out.println() outputs text and then moves to the next line (or just creates a new line when empty)
• The inner loop creates each row of asterisks
• The outer loop creates multiple rows

Common Applications of Nested Loops

1. Processing Two-Dimensional Arrays

Two-dimensional arrays use zero-based indexing where the first element is at index 0. Nested loops are perfect for working with these structures:

// Declare and initialize a 3x4 2D array
int[][] matrix = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// Sum all elements in the 2D array
int sum = 0;
for (int row = 0; row < matrix.length; row++) {
    for (int col = 0; col < matrix[row].length; col++) {
        sum += matrix[row][col];
    }
}
System.out.println("Sum of all elements: " + sum);

2. Pattern Generation

Nested loops can create various patterns by varying the inner loop bounds:

// Create a right triangle pattern
for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print("* ");
    }
    System.out.println();
}

Output:

* 
* * 
* * * 
* * * * 
* * * * * 

3. Finding All Possible Combinations

Nested loops can generate all possible pairings between two sets:

String[] fruits = {"Apple", "Banana", "Cherry"};
String[] colors = {"Red", "Green", "Blue"};

for (int i = 0; i < fruits.length; i++) {
    for (int j = 0; j < colors.length; j++) {
        System.out.println(fruits[i] + " - " + colors[j]);
    }
}

Output:

Apple - Red

Apple - Green

Apple - Blue

Banana - Red

Banana - Green

Banana - Blue

Cherry - Red

Cherry - Green

Cherry - Blue

Control Flow in Nested Loops

We can control the execution flow within nested loops using Boolean expressions and special statements:

Using Boolean Variables for Control

A Boolean variable can signal when to stop iterating:

boolean found = false;
int[][] numbers = {{5, 2, 8}, {9, 7, 1}, {3, 4, 6}};
int target = 7;

for (int i = 0; i < numbers.length && !found; i++) {
    for (int j = 0; j < numbers[i].length && !found; j++) {
        if (numbers[i][j] == target) {
            System.out.println("Found " + target + " at position [" + i + "][" + j + "]");
            found = true;
        }
    }
}

The Continue Statement

The continue statement skips the rest of the current iteration and moves to the next iteration:

// Print a multiplication table but skip multiples of 5
for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
        if ((i * j) % 5 == 0) {
            continue;  // Skip multiples of 5
        }
        System.out.print((i * j) + "\t");
    }
    System.out.println();
}

Nested Loop Efficiency

Nested loops multiply the number of iterations, which affects performance:

For large data sets, consider:

• Avoiding unnecessary iterations
• Breaking out of loops early when possible
• Using more efficient algorithms when applicable

Common Nested Loop Patterns

Pattern 1: Processing All Pairs

// Process all pairs of elements from an array
int[] values = {3, 7, 2, 9};
for (int i = 0; i < values.length; i++) {
    for (int j = 0; j < values.length; j++) {
        if (i != j) {  // Avoid pairing an element with itself
            System.out.println("Pair: " + values[i] + ", " + values[j]);
        }
    }
}

Pattern 2: Processing Unique Pairs

// Process only unique pairs (avoid duplicates like (a,b) and (b,a))
int[] values = {3, 7, 2, 9};
for (int i = 0; i < values.length; i++) {
    for (int j = i + 1; j < values.length; j++) {
        System.out.println("Unique pair: " + values[i] + ", " + values[j]);
    }
}

Pattern 3: Building Triangular Patterns

// Create a number triangle
for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print(j + " ");
    }
    System.out.println();
}

Output:

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 

Complex Examples

Example 1: Finding Prime Numbers

// Print prime numbers up to 50
System.out.println("Prime numbers up to 50:");
for (int num = 2; num <= 50; num++) {
    boolean isPrime = true;
    
    for (int divisor = 2; divisor <= Math.sqrt(num); divisor++) {
        if (num % divisor == 0) {
            isPrime = false;
            break;
        }
    }
    
    if (isPrime) {
        System.out.print(num + " ");
    }
}

Example 2: Matrix Multiplication

// Multiply two matrices
int[][] matrixA = {{1, 2, 3}, {4, 5, 6}};         // 2x3 matrix
int[][] matrixB = {{7, 8}, {9, 10}, {11, 12}};    // 3x2 matrix
int[][] result = new int[matrixA.length][matrixB[0].length];  // 2x2 matrix

// Matrix multiplication
for (int i = 0; i < matrixA.length; i++) {
    for (int j = 0; j < matrixB[0].length; j++) {
        for (int k = 0; k < matrixA[0].length; k++) {
            result[i][j] += matrixA[i][k] * matrixB[k][j];
        }
    }
}

// Print the result matrix
for (int i = 0; i < result.length; i++) {
    for (int j = 0; j < result[0].length; j++) {
        System.out.print(result[i][j] + " ");
    }
    System.out.println();
}

Example 3: Pascal's Triangle

// Generate Pascal's Triangle with 6 rows
int rows = 6;
for (int i = 0; i < rows; i++) {
    // Print spaces for formatting
    for (int space = rows; space > i; space--) {
        System.out.print(" ");
    }
    
    int number = 1;
    for (int j = 0; j <= i; j++) {
        System.out.print(number + " ");
        number = number * (i - j) / (j + 1);
    }
    System.out.println();
}

Common Pitfalls and How to Avoid Them

1. Infinite Loops

Make sure that loop conditions will eventually become false:

// Potentially infinite if i is never set to 5
int i = 0;
while (i != 5) {
    i += 2;  // If i starts at 0, it will always be even and never reach 5
}

// Fixed version
int i = 0;
while (i < 10) {
    if (i == 5) {
        break;
    }
    i += 2;
}

2. Off-by-One Errors

Be careful with loop bounds, especially with zero-based indexing:

// Correct way to process a 3x3 matrix
int[][] matrix = new int[3][3];
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        // Process matrix[i][j]
    }
}

3. Loop Variable Modification

Avoid modifying loop control variables inside the loop body:

// Problematic - modifying the loop variable inside the loop

for (int i = 0; i < 10; i++) {
    // Don't do this:
    if (someCondition) {
        i += 2;  // Unexpected behavior
    }
}

// Better approach
for (int i = 0; i < 10; i++) {
    if (someCondition) {
        // Use continue or other logic instead
        continue;
    }
}

Key Takeaways

• Nested iteration involves placing one loop inside another
• The inner loop completes all its iterations for each single iteration of the outer loop
• For loops are commonly used for nested iteration when the number of iterations is known
• Zero-based indexing is used for arrays, where the first element is at index 0
• Nested loops are essential for working with 2D structures and generating combinations
• System.out.print and System.out.println can be used together to create formatted output
• Boolean variables and the continue statement can control execution flow
• Be mindful of efficiency as nested loops multiply the number of iterations

Mastering nested loops allows you to solve complex problems involving multi-dimensional data structures and create sophisticated algorithms. By understanding the execution flow and common patterns, you can implement elegant solutions to a wide range of programming challenges.