Skip to content

Break and Continue

Learning Objectives

At the end of this sub-unit, students should

  • appreaciate the way to minimize computation by stopping loop prematurely.
  • understand the behavior of break.

Preliminary

Before continuing, you should ensure that you understand how loop behaves because we will be expanding on the concept. If you are not familiar with loop or how to trace loop, you may want to revisit the previous unit first.

Up To n Repetitions

There are cases where we may want to exit a loop before \(n\) repetitions. However, we want the worst-case to still be \(n\) repetition. This usually happens when we found either a solution or a counter-example to our problem. Consider the case of checking if a number is prime or composite.

Prime Number

A number \(n \geq 2\) is a prime number if \(n\) is not a product of two smaller natural numbers.

Even if we assume that \(n \geq 2\), this definition is rather hard to work with. So the first step in trying to solve this is to try to come up with an equivalent definition that is more computational. The keyword here is product. If we look at the inverse of a product, we can rephrase the definition as follows.

A number \(n \geq 2\) is a prime number if \(n\) is not divisible by numbers between 2 and \(n - 1\).

This is something we can deal with because we can have a loop that basically enumerate the values between 2 and \(n - 1\). In other words, we start from i = 3 and we stop when i == n. Since we are interested in the condition to keep the loop going, the condition is actually i < n. But here is the interesting thing, if we find that n is divisible by i, we actually have a counter-example. So the number n is not a prime, but a composite number. The solution to this is to first assume that n is a prime number and if we have a counter-example, then we are sure that n is not a prime.

Prime

1
2
3
4
5
6
7
8
# Assume n is initialized
is_prime = True       # assume a prime
i = 2                 # check from i =2
while i < n:          # check until i = n-1
  if n % i == 0:      # if n is divisible by i
    is_prime = False  # then our assumption is wrong
  i = i + 1           # check next i
print(is_prime)

Note the curious property about this loop-body. The variable is_prime is only ever re-assigned to False. Although it may be re-assigned to False multiple times, we only ever actually need to do this once. So what can we do? Another attempt is to use is_prime as part of the loop-condition.

Prime

1
2
3
4
5
6
7
8
# Assume n is initialized
is_prime = True
i = 2
while i < n and is_prime:  # also stop if is_prime == False
  if n % i == 0:
    is_prime = False
  i = i + 1
print(is_prime)

Luckily, this condition is simple. But there may be other conditions that are harder to be incorporated into the loop-condition. Is there a more generic way? There is a special keyword that can only ever be used inside a loop called break. When this keyword is encountered, the code will exit the nearest loop. Using this new keyword, we can rewrite the code as follows.

Prime

1
2
3
4
5
6
7
8
9
# Assume n is initialized
is_prime = True
i = 2
while i < n:
  if n % i == 0:
    is_prime = False
    break             # jump to Line 9  --+
  i = i + 1           #                   |
print(is_prime)       # <-----------------+ here

This is the form of a loop that will repeat the loop-body \(n\) times at the worst-case. However, under some circumstances, the loop may be shorter than \(n\) repetition.

Bad Practice

Unfortunately for us the else keyword can actually be attached to a loop. The following code is accepted in Python and is actually correct!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Assume n is initialized
i = 1
while i < n - 1:
  i = i + 1
  if n % i == 0:
    is_prime = False
    break
else:
  is_prime = True
print(is_prime)

The interesting thing is that at Line 8, the indentation level of the else keyword is actually the same as while keyword at Line 3. This means that the else keyword is actually attached to the while at Line 3 instead of if at Line 5. The behavior of this else is that it is executed only when the loop terminates normally. By normal termination, it means that we terminate not because of a break. However, it is generally a bad practice to use else on loop because a slight indentation mistake will cause the code to be wildly wrong.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Assume n is initialized
i = 1
while i < n - 1:
  i = i + 1
  if n % i == 0:
    is_prime = False
    break
  else:     # attached to if at Line 5
    is_prime = True
print(is_prime)

The error is even very hard to detect. If we randomly check the output, we will see that all values of \(n \geq 3\) will produce the correct result. The only problem is when \(n = 2\).

Nearest Loop

To determine the nearest loop, we need to keep going up the lines. However, there are some rules we need to obey.

  1. We need to be sure that the break keyword is indeed inside the loop.
  2. As we go up the lines, we can go out into the outer block (i.e., we go into blocks with fewer indentation level).
  3. We cannot go into another inner block. But this inner block is computed from the line directly below it.

The combination of the second and third rule means that the indentation level decrease but never increase. Let us illustrate this with an example. Consider the code below. Think carefully about which is the nearest loop from the break keyword. Then check if your answer is correct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
while cond1:
  pass
while cond2
  while cond3:
    while cond4:
      ...
    if cond:
      break
    while cond5:
      ...
while cond6:
  pass

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
while cond1:
  pass
while cond2
  while cond3:    # <--- nearest loop
    while cond4:
      ...
    if cond:
      break
    while cond5:
      ...
while cond6:
  pass

Note that we can only jump out of the nearest loop. This means that we cannot jump out of multiple loops. In the example above, note that the nearest loop is still within an outer loop. However, the location of the break statement prevents us from even jumping out of this outer loop. To do that, we need to have an additional break statement such that while cond2: is the nearest loop.

We will illustrate the behavior of break with a simple code. Try to trace the execution with a trace table, guess the output, and check if your understanding is correct.

1
2
3
4
5
6
7
8
9
i = 0
while i < 5:
  j = i
  while j < 5:
    if j == 3:
      break
    print(i, j)
    j = j + 1
  i = i + 1

1
2
3
4
5
6
7
8
9
i = 0
while i < 5:
  j = i
  while j < 5:  # <--- nearest loop
    if j == 3:
      break
    print(i, j)
    j = j + 1
  i = i + 1

1
2
3
4
5
6
7
8
9
i = 0
while i < 5:
  j = i
  while j < 5:
    if j == 3:
      break      # ----+
    print(i, j)  #     |
    j = j + 1    #     |
  i = i + 1      # <---+
Outer Iter Inner Iter i2 j4 j == 3 print(i, j)
1 1 0 0 False 0 0
1 2 0 1 False 0 1
1 3 0 2 False 0 2
1 4 0 3 True  
2 1 1 1 False 1 1
2 2 1 2 False 1 2
2 3 1 3 True  
3 1 2 2 False 2 2
3 2 2 3 True  
4 3 3 3 True  
5 1 4 4 False 4 4 
1
2
3
4
5
6
7
0 0
0 1
0 2
1 1
1 2
2 2
4 4

Continue

Optional Knowledge

There is the "dual" of break that can also only be used in a loop called continue. Unlike break, the keyword continue will actually let us jump back to the beginning of the loop (i.e., the loop-condition). This will bypass the rest of the code in the loop-body.

1
2
3
4
while loop_cond: # <----------------------+ here
  if if_cond:    #                        |
    continue     # jump back to Line 1  --+ we skip Line 4
  block