CS211: Loops

Oftentimes we run into situations where we would like to repeat the same computation multiple times. As an example, consider a program which computes the power of one number raised to another. We know that 3^8 is equivalent to 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3. This would be easy enough to hard code¹. We could write the following C program:

1: #include <stdio.h>
2: int main(){
3:   int val = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3;
4:   printf("3^8 = %d\n", val);
5: }

And it works well enough, printing the expected 3^8 = 6561. But what if 3 and 8 weren't constant values, but variables? If I replace 3 with x:

1: #include <stdio.h>
2: int main(){
3:   int x = 3;
4:   int y = 10;
5:   int val = x * x * x * x * x * x * x * x;
6:   printf("%d^%d = %d\n", x, y, val);
7: }

If we run the above, we don't get the expected 3^10 = 59049, but 3^10 = 6561! It's clear that because Line 5 does not adapt to the fact that the target power has changed there can be no alteration in the computational task. One way we can fix this is with looping.

There are three looping constructs provided by the C programming language, two of which are slight variatios on the foundational while loop. The syntax of a while loop is as follows:

1: while(condition)
2:   block; // Do this

Pretty simple! While a certain condition is met, i.e. the expression resolves to true, the instructions in the block will be executed. Once the instructions in the block have been exhausted the condition is checked again. If it is met the instructions start over (hence the "loop"); if the condition is not met the next set of instructions outside of the loop will be executed.

Here's how we can modify the power example to work with a while loop:

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;       // Base
 4:   int y = 10;      // Target power
 5:   int pow = 1;     // Starting accumulator value
 6:   int i = 0;       // Iterator
 7:   while(i < y){    // Conditional check
 8:     pow = pow * x; // Computation
 9:     i = i + 1;     // Incrementing i to eventually satisfy looping condition
10:   }
11:   printf("%d^%d = %d\n", x, y, pow);
12: }

There's a lot going on here. First, you'll notice there are two more variables: pow and i. pow is an accumulator which stores the partial result of each computational step needed to get the final power value. i acts as a tally that keeps track of how many loops have been performed. Additionally, you can see that there's some new logic: a conditional operator i < y and a code block. The conditional is used to limit the number of loops performed (more on this later), and the code block is for defining a set of computations to be performed each loop. Here, the code block is multiplying the pow accumulator with the base x and incrementing the i loop tally. We can trace the value at the end of every loop for each variable in a table to keep track of what's happening:

After the 10th loop completes the conditional is checked on final time. Since i is now equal to 10 the expression i < 10 resolves to false and control is transferred to the first block outside of the loop, which is the print function call.

The last looping structure provided by C is likely also it's most famous: the for loop. The syntax for the for loop is as follows:

1: for(expr1 ; expr2 ; expr3)
2:   block; // Do something

expr1 is the declaration expression. It is where you can define or set a variable at the entrance of the for loop. expr2 is the conditional expression. It is where you can place the conditional check that will be used to determine if another loop will be completed. expr3 is the increment expression. It is used for performing an additional operation at the end of the loop that is not included in the block body. expr1, expr2, and expr3 are all optional.

When expr2 is not present it will be treated as a true value. This means that for(;;) is equivalent to a while(1) statement.

Here is an example of the power program with a for loop:

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;                        // Base
 4:   int y = 10;                       // Target power
 5:   int pow = 1;                      // Starting accumulator value
 6:   for(int i = 0; i < y; i = i + 1){ // Declaration, conditional check, and increment expression
 7:     pow = pow * x;                  // Computation
 8:   }
 9:   printf("%d^%d = %d\n", x, y, pow);
10: }

Both Listing 4 and Listing 11 are functionally equivalent². The obvious change is that the loop tallying variable, i, has been declared in expr1 and is incremented in expr3. Everything else is identical.

Many people prefer to write for loops over while loops due to convenience. From the compiler's perspective, it often does not matter.

Additions like the for loop and the do while loop can be classified as syntactic sugar. They do not provide additional functionality for the language, but they provide stylisitic benefits.

Loops can be nested within one another. For example, if I wanted to print out a 4x3 grid of asterixes I could write:

1: #include <stdio.h>
2: int main(){
3:   for(int i = 0; i < 4; i++){
4:     for(int j = 0; j < 3; j++){
5:       printf("*");
6:     }
7:     printf("\n");
8:   }
9: }

There are many situations where nested for loops are desirable, particularly with complex data structures.

We can use the break statement that we learned about with the switch statement. break will immediately transfer control out of the loop to the next block available as if the condition failed. If we did not want our power function to iterate anymore if pow was greater than 100:

 1: #include <stdio.h>
 2: int main(){
 3:   int x = 3;       // Base
 4:   int y = 10;      // Target power
 5:   int pow = 1;     // Starting accumulator value
 6:   int i = 0;       // Iterator
 7:   while(i < y){    // Conditional check
 8:     pow = pow * x; // Computation
 9:     if(pow > 100)
10:       break;       // Exists the loop
11:     i = i + 1;     // Incrementing i to eventually satisfy looping condition
12:   }
13:   printf("%d^%d = %d\n", x, y, pow);
14: }

I leave it as an exercise to you to see what happens when the above is ran.

Similarly to the break keyword, the continue keyword alters the control flow of a loop. When a continue is reached control flow will be transferred to the "end" of the loop. For a while loop that means the conditional will immediately be rechecked. For a for loop that means the increment expression will be performed then the conditional will be checked. Here is a for loop that sums up all even numbers from 1 to 100:

 1: #include <stdio.h>
 2: int main(){
 3:   int sum = 0;
 4:   for(int i = 0; i < 100; i++){
 5:     if(i % 2 == 1)
 6:       continue;
 7:     sum = sum + i;
 8:   }
 9:   printf("sum = %d\n", pow);
10: }

1. Rewrite the power program from Listing 4 using a for loop instead of a while loop. Then rewrite it again using a do while loop. Which version do you find most readable and why?

2. The lecture provides a trace table for Listing 4 showing the value of i and pow at the end of each loop. Construct a similar trace table by hand for the following program, then verify by running it:

   int x = 2;
   int y = 8;
   int pow = 1;
   int i = 0;
   while(i < y){
       pow = pow * x;
       i = i + 1;
   }
   

3. Write a for loop that computes the sum of all integers from 1 to 100. Then write the equivalent using a while loop. Verify both produce the same result.
4. The lecture states that for(;;) is equivalent to while(1). Write a program using each form that prints "looping…" exactly 5 times using a break statement to exit. Verify both behave identically.
5. Modify the even sum program from Listing 14 to instead sum all odd numbers from 1 to 100 using continue. What change do you need to make to the conditional? Verify your result.
6. The lecture notes that the compiler does not warn about infinite loops. Write a program containing an infinite loop as shown in Listing 5, compile it with gcc, and confirm no warning is produced. Then use Ctrl+C in the terminal to kill it. What does Ctrl+C do at the OS level?
7. Write a for loop using the break keyword that finds the first integer greater than 1 whose square exceeds 500. Print both the integer and its square.
8. The lecture shows the assembly output for the while loop in Listing 6. Compile the for loop version of the power program from Listing 11 with gcc -O0 -fno-omit-frame-pointer -fno-stack-protector -S and compare the assembly output. Are they identical? What does this tell you about the relationship between for and while loops at the machine level?

9. Using nested loops as shown in Listing 12, write a program that prints the following multiplication table:

   1  2  3  4  5
   2  4  6  8  10
   3  6  9  12 15
   4  8  12 16 20
   5  10 15 20 25
   

10. The lecture states that all three expressions in a for loop are optional, as shown in Listing 10. Write three separate programs demonstrating this: one with expr1 omitted, one with expr3 omitted, and one with both omitted. In each case, what change must you make elsewhere to keep the program correct?