Overview of Unit 4: Iteration and 4.1 While Loops

The Big Takeaway Of This Unit

Iteration Using loops, we can do a statement repeatedly and this can lead to the creation of many complex algorithms.

Unit Overview

Exam Weighting

• 17.5-22.5% of the test
• Roughly 7 to 9 multiple-choice questions
• A part of FRQ #1, which tests your ability to write methods using control structures, including loops.

Enduring Understanding

Now that we have finished branching and conditionals, it's time to add the final element of our algorithm toolbox: iteration. Iteration is a way to simplify code that would otherwise be repeated many times in succession. Using loops, we can finally implement complex algorithms and solutions to common problems that we weren't able to before. In this unit, we will learn two types of loops: the while loop and the for loop.

Building Computational Thinking

When we code, we need to make sure that our loops run exactly the number of times that they are supposed to or else, it may just throw you for a loop! We can do this by checking the loop conditions and the incrementation inside our loops. 

Loops can face other problems such as having no end (an infinite loop) or returning the wrong result. We will be learning a method that may help us in making sure our loop works! Combining these with the branching methods we learned in the last unit, we can make many complex algorithms.

Main Ideas for This Unit

• While Loops
• For Loops
• String Traversals
• String Algorithms
• Nested Iterations
• Tracing

4.1: While Loops

What is Iteration?

This unit is all about iteration, the act of repeating an action or set of actions until a given condition is met. This is done using loops, the control structure that allows you to perform iteration. There are two types used in this unit: the while loop and the for loop. We will learn about a third type, in Unit 6, called the enhanced for loop.

Introduction to While Loops

The first type of loop we will learn about is the while loop. While loops keep running while a condition is true. Here is the anatomy of the while loop:

code before loop
while (condition) {
  do this while the condition is true
}
do this when the condition is no longer true

The condition is a boolean statement like the ones we learned about in Unit 3, and the loop body follows. In the loop body, the statement is repeated while the condition is true. Once the condition is no longer true, we have exited the loop. 

However, there is another way to exit the loop. If there is a return statement inside the loop body, the loop and method are automatically exited.

Possible Issues With Loops

When making loops, we can have a problem with the loop condition if it never changes. There are two cases as follows: Loop Condition Always True

If the loop condition is always true, then the loop will never exit, and we are in what is known as an infinite loop. One can be created by setting the condition as just "true" or forgetting to change something in the loop body that makes the condition false. An infinite loop can easily crash a computer and server depending on the program and should be avoided at all costs. If you have run a program and hit an infinite loop, use ctrl+c to stop the program immediately in your programming environment.

Loop Condition Always False

If the loop condition is always false, then the loop will never run, and the loop body is just skipped. College Board will sometimes put these conditions on the multiple-choice portion of the exam. But, in practice, this leads to inefficiencies and leads to larger code file sizes than necessary. Thus, we should carefully check the loop conditions to make sure that this doesn't happen.

While Loop Structures

Using the general structure of a while loop, it is possible to make general templates based on how we want the loop to work. There are different types based on the structure of the while loop condition:

Fixed Number of Repetitions

In order to use a fixed number of repetitions, we use an integer set up to be a counter. The general structure of this is as follows:

int i = 0;
while (i < numberOfRepetitions) {
  do something
  i++;
}

We use the integer i as an increment, because it increments by 1 every time the loop is run. The line i++; is very important because if it isn't there, the loop condition will always be true and an infinite loop is created.

Variable Number of Repetitions Using A Sentinel

This method is used whenever we want to enter a set of inputs using the Scanner class from the Unit 1 guide. We want the to program to stop asking for inputs when we enter an input that meets a certain criteria. This particular input is called the sentinel. Here is its structure for a loop that stops if "***" is entered:

import java.util.Scanner;

System.out.print("Enter a list of names, hitting enter/return between each one. \"***\" to stop");
Scanner input = new Scanner(System.in);
String name = input.nextLine();
while(!name.equals("***")) {
  do something
  String name = input.nextLine();
}

Notice how we have the first name inputted before the loop begins and at the end of each iteration instead of the beginning. This is done in order to have an input to check against the sentinel "***". If the sentinel is encountered, then nothing else is done — the loop breaks!

Variable Number of Repetitions Using A Flag

Other times, we don't enter different inputs, but we keep running until a certain action is met inside the loop. This is done using a flag that marks when this condition is met and exits the loop if and when it is met. Here is its structure:

boolean flag = true;
while (flag) {
  do something
  if (some condition is met) {
    flag = false;
  } else {
    keep doing stuff
  }
}

Note how we set the flag to true and only set it to false once the condition is met. Because the flag is now false, the loop will stop as well.

Making Sure Your Loop Works: The Four Loopy Questions

The four loopy questions are a modified version of those taught at Professor David Gries's CS 2110 class taught at Cornell University.

How do we ensure that our loop works correctly? Well here is a set of four questions that may help you with this!

1. Does my loop start right?
2. Does my loop end right?
3. Does my loop make progress towards completion?
4. Will the method break in the middle of the loop?

Break and Continue

Two statements that will help us with loops are the break and continue statements.

The break statement will immediately exit out of the loop, no matter if the loop condition is still true. Using this, we can have an alternative code snippet for the flagged loop.

while (true) {
  do something
  if (certain condition is met) {
    do something else
    break;
  }
  do something if condition not met
}

In contrast, the continue statement jumps to the next iteration of the loop and doesn't complete the current one. For example, if we want to add all the numbers from 0 to 10 but not include 4, we would do the following:

public static int sampleSum() {
  int i = 0;
  int sum = 0;
  while (i <= 10) {
    if (i == 4) {
      continue;
    }
    sum += i;
  }
  return sum;
}

Try-Catch Statements and Exception Handling

When coding, especially when using loops, we want our code to be robust, meaning that it has to respond correctly and not crash, no matter what input we give it. Normally, if we give invalid input, we will get an InputMismatchException or another error type and the program will crash. Instead, we want our program to continue, or at least end "nicely" where it doesn't instantly crash. This is where we use try-catch statement blocks and exception throwing. Together, these make up Java exception handling.

Exceptions are signs that something is wrong with the code at runtime (when the program is running) and, without try-catch statements, the program crashes. There are two types of methods that deal with exception handling. Some methods throw an exception for other methods to detect. These other methods will do something about this exception so that the program continues smoothly. We will first talk about the former.

Some methods can throw an exception, which is when an exception is encountered and the exception is flagged for another method to catch and fix, which is what throwing an exception means. If no other methods have a way to catch the exception, the program crashes.

Meanwhile, other methods can catch exceptions and handle them so that the program doesn't crash. The program tries to run a program assuming that it works correctly in a try block, and if it catches an exception, the program moves to a catch block. A method can have multiple catch blocks, each to catch a different type of exception. However, there is a finally block that runs afterwards regardless of what is in the try or catch blocks. Here is the structure of two methods, one which throws an exception and another that catches exceptions.

public static int exceptionThrower() throws InputMismatchException {
  some code
  if (conditionForErrorMet) {
    throw InputMismatchException;
  }
  return 1;
}

public static void exceptionHandler() {
  some code
  try {
    some code that is tried
    int i = exceptionThrower()
  } catch (InputMismatchException i) {
    do something if there is an InputMismatchException
  } catch (Exception e) {
    do something if there is another type of exception
  } finally {
    code that is run regardless
  }
}

Algorithms Using While Loops

Using the building blocks of while loops and some of what we just learned, we can make some algorithms that can do various tasks. Here are some common algorithms illustrated with various code snippets:

Finding Divisibility Without Modulo

Note: This works only for positive numbers and will throw an exception if the inputs do not meet this requirement.

public static boolean divisibility(int number, int divisor) throws NumberFormatException {
  if (number < 0 || divisor <= 0) {
    throw NumberFormatException;
  } else if (number == 0) {
    return true;
  } else {
    while (number > 0) {
      number -= divisor;
    }
    if (number == 0) {
      return true;
    } else {
      return false;
  }
}

Finding the Digits in an Integer From Small to Large Magnitude

Note: This works only for positive numbers and will throw an exception if the input does not meet this requirement.

public static void return digits(int number) throws NumberFormatException {
  while (number != 0) {
    System.out.println(number%10 + " ");
    number /= 10
  }
}

Determining Frequency of a Condition

import java.util.Scanner;

public static int determineFrequencyOfEvens() {
  Scanner input = new Scanner(System.in);
  int number;
  int frequency = 0;
  System.out.println("Enter a sequence of integers line by line. Enter 000 to end");
  try {
    number = input.nextInt();
    while (number != 000) {
      if (number % 2 == 0) {
        frequency++:
      }
      number = input.nextInt();
    }
  } catch (Exception e) {
    System.out.println("Invalid input. Terminating input sequence");
  } finally {
    return frequency;
  }
}
      

Determine a Minimum from Inputs

import java.util.Scanner;

public static int determineFrequencyOfEvens() {
  Scanner input = new Scanner(System.in);
  int number;
  int min;
  System.out.println("Enter a sequence of integers line by line. Enter 000 to end");
  try {
    number = input.nextInt();
    min = number;
    while (number != 000) {
      if (number < min) {
        min = number:
      }
      number = input.nextInt();
    }
  } catch (Exception e) {
    System.out.println("Invalid input. Terminating input sequence");
  } finally {
    return min;
  }
}

Determine a Maximum from Inputs

import java.util.Scanner;

public static int determineFrequencyOfEvens() {
  Scanner input = new Scanner(System.in);
  int number;
  int max;
  System.out.println("Enter a sequence of integers line by line. Enter 000 to end");
  try {
    number = input.nextInt();
    max = number;
    while (number != 000) {
      if (number > max) {
        max = number:
      }
      number = input.nextInt();
    }
  } catch (Exception e) {
    System.out.println("Invalid input. Terminating input sequence");
  } finally {
    return max;
  }
}

Computing a Sum from Inputs

import java.util.Scanner;

public static int determineFrequencyOfEvens() {
  Scanner input = new Scanner(System.in);
  int number;
  int sum = 0;
  System.out.println("Enter a sequence of integers line by line. Enter 000 to end");
  try {
    number = input.nextInt();
    while (number != 000) {
      sum += number;
      number = input.nextInt();
    }
  } catch (Exception e) {
    System.out.println("Invalid input. Terminating input sequence");
  } finally {
    return sum;
  }
}

Computing an Average from Inputs

import java.util.Scanner;

public static int determineFrequencyOfEvens() {
  Scanner input = new Scanner(System.in);
  int number;
  int sum = 0;
  int counter = 0;
  System.out.println("Enter a sequence of integers line by line. Enter 000 to end");
  try {
    number = input.nextInt();
    while (number != 000) {
      sum += number;
      counter ++;
      number = input.nextInt();
    }
  } catch (Exception e) {
    System.out.println("Invalid input. Terminating input sequence");
  } finally {
    return (double) sum / counter;
  }
}