The Nested Loop

Understanding Nested Loops

Nested loop occurs when one or more loops are placed inside another loop. These types of loops can handle more complex flow of executions and repetitions compared to a single loop. Nested loops are useful when you are working with multidimensional arrays, performing matrix operations, and implementing nested structures.

Syntax

The basic syntax of a nested loop involves an outer loop and an inner loop. 

• Outer loop: is placed outside and controls the overall flow. 
• Inner loop: is placed inside the outer loop and therefore, it completes a cycle of iterations for each iteration of the outer loop. 

This is how a “nested for loop” structure looks like:

// Outer loop
for (outer_initialization; outer_condition; outer_update) {
    // Inner loop
    for (inner_initialization; inner_condition; inner_update) {
        // Loop body
    }
}

Flow of execution of nested loops

The flow of execution of nested loops is evident due to its hierarchical structure:

1. Outer loop executes its entire cycle. 
2. Inner loop completes its cycle for each iteration of the outer loop. 
3. Innermost statements (inside the inner loop) will be executed sequentially.

For example, if the outer loop executes 5 times, and the inner loop completes its cycle in 3 iterations, then for each iteration of the outer loop, the inner loop completes its cycle. This means the inner loop will execute 5 * 3 = 15 times. In this way, the innermost statements will execute a total of 15 times. 

Example

Let’s explore a simple example to print a 3×3 matrix:

#include <stdio.h>

int main()
{
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            printf("(%d %d) ", i, j);
        }
        printf("\n");
    }
    return 0;
}

Output: 

(1 1) (1 2) (1 3)
(2 1) (2 2) (2 3)
(3 1) (3 2) (3 3)

Let’s understand why we are getting this output. Every first element in the Matrix is obtained from the outer loop and the second element is obtained from the inner loop. For i = 1, the inner for loop will execute 3 times. That’s why in the first row, we got (1 1) (1 2) (1 3). As the inner loop has completed one cycle, the printf() function following it will be executed which is responsible for printing a newline. This is the reason why the second row is printed in its own line. For the second iteration of the outer loop i.e. for i = 2, the inner loop will execute 3 times, so we will get (2 1) (2 2) (2 3). Remember that the second time, variable j is again initialized to 1, that’s why we get values 1, 2, and 3 as the second elements in the second row as well. Following the same pattern, the third row will be displayed.

Considerations and Potential Issues

Nested loops are good in implementing complex iterations but excess usage of these structures may reduce the readability of the code. So, use them wisely in your code. Also, they are computationally expensive compared to single loops, so if program’s execution time is a concern then consider solving the problem with a single loop. Although it is difficult in practice for most situations, being conscious about the intricacies of the nested loops will force you to go for computationally inexpensive solutions whenever possible.

Level-Up Your Understanding

Question 1:  How many times will the following nested loop execute?

for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= i; j++) {
            // Do something
        }
}

Answer:  The condition of the inner loop depends upon the current value of i in the outer loop. 

For i = 1, the inner loop executes 1 time. 
For i = 2, the inner loop executes 2 times. 
For i = 3, the inner loop executes 3 times. 
For i = 4, the inner loop executes 4 times. 
For i = 5, the inner loop executes 5 times. 

So, the total number of times the nested loop executes is 1+2+3+4+5 = 15 times.

Question 2:  Determine the output of the following code:

#include <stdio.h>

int main()
{
    int x = 5;
    while (x > 0) {
        for (int y = 1; y <= x; y++) {
            printf("%d ", y);
        }
        printf("\n");
        x--;
    }
    return 0;
}

Answer:  The output of the above program is 

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

Why?

When x is 5, the inner loop will execute 5 times because the condition within the inner loop depends upon the value of x. Due to this reason, the first row is having values 1 2 3 4 5. Similarly, when x is 4, the inner loop executes 4 times, and that is why in the output, the second row has values 1 2 3 4. In this way, the remaining rows are filled. 

Question 3:  Determine the output of the following program:

#include <stdio.h>

int main() {
    int i;
    for (int i = 1, j = 2, k = 1; i % 5 != 0;) {
        while (j != 0) {
            do {
                printf("%d ", i + k);
                k *= 2;
            } while (k < 33);
            j--;
        }
        i++;
    }
}

Answer:  The output of the above program is

2 3 5 9 17 33 65

Why?

Let’s analyze the program step by step to understand how the program works:

1. The program starts with ‘i’ initialized to 1, ‘j’ initialized to 2, and ‘k’ initialized to 1.
2. The outer ‘for’ loop runs as long as the condition ‘i % 5 != 0’, meaning it continues until ‘i’ is divisible by 5. 
3. Inside the ‘for’ loop:
   1. The ‘while’ loop runs until ‘j’ becomes 0.
   2. Inside the ‘while’ loop:
      1. The ‘do-while’ loop executes at least once and continues until ‘k’ is greater than or equal to 33.
      2. Inside the ‘do-while’ loop:
         1. It prints the value of ‘i + k’.
         2. Then it multiplies ‘k’ by 2.

Let’s now understand how the numbers are generated:

• When i = 1, j = 2, and k = 1
  • The do-while loop prints i + k which is 2.
  • Then it multiplies k by 2, making it 2.
  • The variable j is decremented to 1.
  • Since k is less than 33, the do-while loop continues.
  • It prints i + k which is 1+2 = 3.
  • Then it multiplies k by 2, making it 4. 
  • Since k is less than 33, the do-while loop continues.
  • It prints i + k which is 1+4 = 5.
  • Then it multiplies k by 2, making it 8.
  • Since k is less than 33, the do-while loop continues.
  • It prints i + k which is 1+8 = 9.
  • Then it multiplies k by 2, making it 16.
  • Since k is less than 33, the do-while loop continues.
  • It prints i + k which is 1+16 = 17.
  • Then it multiplies k by 2, making it 32.
  • Since k is less than 33, the do-while loop continues.
  • It prints i + k which is 1+32 = 33.
  • Then it multiplies k by 2, making it 64.
  • Now, k is greater than 33, so the do-while stops.
  • The variable j is decremented by 1, making it 1.
  • The while loop condition is satisfied, so we enter inside the loop.
  • The do-while will execute once, and it prints i + k which 1 + 64 = 65.
  • Then it multiplies k by 2, making it 128.
  • The do-while condition is false, hence we exit from the do-while loop.
  • The variable j is decremented by 1, making it 0.
  • The while loop condition fails, so we exit from the while loop.
  • The variable i is incremented, making it 2.
• The variable i is still not divisible by 5, therefore, we again enter inside the for loop but the inner while loop will not execute because j is zero.
• The pattern continues until ‘i’ becomes 5, at which point the outer ‘for’ loop stops, because ‘i % 5’ equals 0.

So, I hope I made it clear why we got that specific output.

Conclusion

The nested loops can become trickier to decode, but they are very helpful in performing complex operations and repetitions. Once you master the concept, they open up a wide range of possibilities for solving complex problems. The key to understanding nested loops is to break them down into smaller, more manageable pieces. Each loop has a specific purpose, and it’s essential to identify what that purpose is before attempting to decipher the code. 

Overall, nested loops are a versatile tool that can be used to solve a wide range of problems. While they can be challenging to understand at first, with practice, they will become second nature.