Skip to content

Nested Loop

Learning Objectives

At the end of this sub-unit, students should

  • understand how nested iteration works.
  • know how to write nested iteration statement.
  • know how to apply nested iteration statement in problem solving.

ASCII Art

As with selection, we can combine iteration with another iteration. If we have a loop inside a loop, we have a nested loop! The easiest way to illustrate nested loop is via ASCII art. What we will do is to draw some patterns on screen.

As we are trying to illustrate nested loop, all of these patterns can be solved with a single loop by using the string repetition operator *. So let us assume that we do not have such operator. Otherwise, we will have to look for much more complicated problems and that may only cause confusion.

Square

The first pattern we want to draw is the simplest one. Let us draw a square. The square should depend on some variable n. Given n, we draw a square with n rows and n columns.

  • n = 1

    1
    *

  • n = 2

    1
2
    **
**

  • n = 3

    1
2
3
    ***
***
***

  • n = 4

    1
2
3
4
    ****
****
****
****

How should we draw this? Let us first understand how we can draw on a screen. Unlike pen/pencil, the way we draw on a screen is to print using the print function. But recap that the print function print one line at a time. So we need to figure out what need to do at each line.

By comparing the sample run above, we can figure out that at each line, we need to print exactly n number of *. Of course we can use n * '*', but we assume we have no such operation. So what can we do? Well, we need to use another loop to repeatedly concatenate * into a string and print this string.

So let us try to solve this problem of repeated concatenation first.

Constructing a Row

To construct a row, we will need to start with a variable holding the most basic string, which is the empty string. At each iteration, we will need to add one *. Since we need to add exactly n number of *, we can use the fixed repetitions loop as follows.

1
2
3
4
5
6
7
# Assume n is initialized
i = 0
row = ''
while i < n:
  row = row + '*'
  i = i + 1
# row has exactly n number of *

Once we can construct this row, we need to look at the remaining problems.

Printing Each Row

As we can construct a row for a given some n, the remaining problem is to print exactly n rows. We need another loop for this. Within the loop, we will need to construct the row and print it. Assuming we know how to construct a row, the code will look like the following.

1
2
3
4
5
6
# Assume n is initialized
i = 0
while i < n:
  # construct row
  print(row)
  i = i + 1

Combining

So we have two separate codes.

  • Code to construct row of n number of *.
  • Code to print n rows.

The last task is to combine the two. Notice how we use the row construction inside the printing. So we need to copy the first code to the second. Unfortunately, a naïve copy will not work as you can test below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Assume n is initialized
# print rows
i = 0
while i < n:
  # construct row
  # ----------------------------------------
  i = 0
  row = ''
  while i < n:
    row = row + '*'
    i = i + 1
  # row has exactly n number of *
  # ----------------------------------------
  print(row)
  i = i + 1

The interesting question is, why does it fail? We need to become a detective and figure this out. One useful technique we want to introduce is to think about a code in terms of the following.

  • Input: What are assumed to be initialized for the code to work?
  • Output: What is the result of the code and in which variable?
  • Local Variables: What variables are used for correct implementations of the code that is initialized within the code.

This way, we can use a grey box to represent the code1. Of course we need to know what the code is doing, but that can be put as side-note about the code. We do not have to care about how the code is implementing this procedure. We only to know the three aspects of it to be able to compose the code correctly. In the future, we will make this box into a black box by removing local variables from our design.

Using this idea, we can represent the construction of rows as the following grey box.

Grey01

To fully combine the two codes, we need some conventions2. Firstly, we need to consistently rename all variables including inputs and outputs. In this case, because row is not used by the outside, we can keep the name. But let us change the following variables.

  • i is renamed to j.
  • n is renamed to m.

Secondly, we add an initial assignment from input variables to the renamed variable. In this case, let us add an assignment m = n at the beginning. Note that this second step is not necessary if the input variable is never modified by the code.

Renamed Row Construction 
1
2
3
4
5
6
7
m = n
j = 0
row = ''
while j < m:
  row = row + '*'
  j = j + 1
# row has exactly n (or m) number of *

We can now use the renamed version of the row construction code. The combined code should work as intended.

Square

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Assume n is initialized
# print rows
i = 0
while i < n:
  # construct row
  # ----------------------------------------
  m = n
  j = 0
  row = ''
  while j < m:
    row = row + '*'
    j = j + 1
  # row has exactly n (or m) number of *
  # ----------------------------------------
  print(row)
  i = i + 1

In subsequent problems, we will apply the same technique. However, the explanation will not be as thorough. Additionally, some steps may be skipped from the text but it is recommended that you attempt it without skipping any steps.

Left Triangle

Here, the idea is that instead of printing exactly n number of * on each row, we print k number of * where k ranges from 1 to n. So in kth row, we print exactly k number of *.

Sample Run

  • n = 1

    1
    *

  • n = 2

    1
2
    *
**

  • n = 3

    1
2
3
    *
**
***

  • n = 4

    1
2
3
4
    *
**
***
****

Here, we can see how the idea works for n = 5.

1
2
3
4
5
6
7
8
       1  2  3  4  5
k = 1  *                # 1 × '*'
k = 2  *  *             # 2 × '*'
k = 3  *  *  *          # 3 × '*'
k = 4  *  *  *  *       # 4 × '*'
k = 5  *  *  *  *  *    # 5 × '*'

# in general, (k × '*')

Sub-Problems

The grey box is shown below so that we can apply renaming immediately.

Grey02

1
2
3
4
5
6
7
8
# input: k
m = k
j = 0  # local
row = ''
while j < m:
  row = row + '*'
  j = j + 1
# output: row

The other sub-problem is similar. We need to print each row.

1
2
3
4
5
6
7
# input: n
i = 0  # local
while i < n:
  k = i + 1  # row construction input is k
  # row construction
  print(row)
  i = i + 1

Combining

Left Triangle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# input: n
i = 0  # local
while i < n:
  k = i + 1  # row construction input is k
  # row construction
  # ----------------------------------------
  # input: k
  m = k
  j = 0  # local
  row = ''
  while j < m:
    row = row + '*'
    j = j + 1
  # output: row
  # ----------------------------------------
  print(row)
  i = i + 1

Right Triangle

Similar to left triangle, we print exactly k number of *. However, the problem here is that we cannot do a right-aligned print. What we can do instead is to print a whitespace ' ' (i.e., Space).

Sample Run

  • n = 1

    1
    *

  • n = 2

    1
2
     *
**

  • n = 3

    1
2
3
      *
 **
***

  • n = 4

    1
2
3
4
       *
  **
 ***
****

Here, we can see how the idea works for n = 5 by using _ to indicate whitespace.

1
2
3
4
5
6
7
8
       1  2  3  4  5
k = 1  _  _  _  _  *    # (4 × ' ') + (1 × '*')
k = 2  _  _  _  *  *    # (3 × ' ') + (2 × '*')
k = 3  _  _  *  *  *    # (2 × ' ') + (3 × '*')
k = 4  _  *  *  *  *    # (1 × ' ') + (4 × '*')
k = 5  *  *  *  *  *    # (0 × ' ') + (5 × '*')

# in general, ((n - k) × ' ') + (k × '*')

Sub-Problems

Note that we have 2 inputs. We need both n and k. So we add two assignments to accommodate both.

Grey03

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# input: k, n
m1 = k
m2 = n
j = 0  # local
row = ''
# add ' '
while j < m2 - m1:  # (n - k) times
  row = row + ' '
  j = j + 1
# add '*'
j = 0
while j < m1:       # k times
  row = row + '*'
  j = j + 1
# output: row

The other sub-problem is similar. We need to print each row.

1
2
3
4
5
6
7
8
# input: n
i = 0  # local
while i < n:
  k = i + 1  # row construction input is k and n
             # we simply keep n as it is
  # row construction
  print(row)
  i = i + 1

Combining

Right Triangle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# input: n
i = 0  # local
while i < n:
  k = i + 1  # row construction input is k
  # row construction
  # ----------------------------------------
  # input: k, n
  m1 = k
  m2 = n
  j = 0  # local
  row = ''
  # add ' '
  while j < m2 - m1:  # (n - k) times
    row = row + ' '
    j = j + 1
  # add '*'
  j = 0
  while j < m1:       # k times
    row = row + '*'
    j = j + 1
  # output: row
  # ----------------------------------------
  print(row)
  i = i + 1

Inverted Right Triangle

With all the work we have done before, the last problem is actually quite straightforward. We do not even have to modify the row construction code. We can, but we do not have to. The only thing we need to modify is one of the inputs to the row construction for the right triangle problem.

Grey04

The input we have to change is the first input, which is the variable k. In fact, the change is quite simple. We simply change the way k is generated. Instead of generating from 1 upwards to n, we simply reverses this and generate n downwards to 1. So the change is on the row print as highlighted below while the rest of the codes are the same as before.

Inverted Right Triangle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# input: n
i = n  # local: start from n
while i > 0: # down to 1
  k = i      # row construction input is k (but just i)
  # row construction
  # ----------------------------------------
  # input: k, n
  m1 = k
  m2 = n
  j = 0  # local
  row = ''
  # add ' '
  while j < m2 - m1:  # (n - k) times
    row = row + ' '
    j = j + 1
  # add '*'
  j = 0
  while j < m1:       # k times
    row = row + '*'
    j = j + 1
  # output: row
  # ----------------------------------------
  print(row)
  i = i - 1  # by subtraction

Managing Complexity

At this point, you may realize that our code is getting very very complicated. However, from a certain point of view, the solution is rather simple. Take for instance, the inverted right triangle problem above. If we look at it in terms of "simpler problems", then we can write the code as follows with details omitted.

Simpler Problem View

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Procedure: Inverted Triangle
# ----------------------------------------
# input: n
i = n
while i > 0:
  # Procedure: Row Construction
  # ::: Set Up Input :::
  k = i
  n = n
  # ----------------------------------------
  # input: k, n
  #   :  code omitted
  # ----------------------------------------
  # ::: Output Can be Used :::
  print(row)
  i = i - 1
# output: nothing (we print)
# ----------------------------------------

To manage complexities, we need to be able to name the highlighted section and execute the highlighted section when needed. We may not even need to know how the highlighted section is implemented as long as we are sure it is doing the correct thing. In fact, we can even replace the # : code omitted section with string repetition.

Changing Row Construction

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Procedure: Inverted Triangle
# ----------------------------------------
# input: n
i = n
while i > 0:
  # Procedure: Row Construction
  # ::: Set Up Input :::
  k = i
  n = n
  # ----------------------------------------
  # input: k, n
  row = ((n - k) * ' ') + (k * '*')
  # ----------------------------------------
  # ::: Output Can be Used :::
  print(row)
  i = i - 1
# output: nothing (we print)
# ----------------------------------------

In fact, we have done something like this before. When we invoke the print function, we do not need to know how the print function is implemented. What we want is to create our own function. This we will learn in the future. But for now, simply note that problems can often be simpler if we think in terms of "simpler problems" and not the details.

That is what we are going to do going forward. We will describe problems in terms of simpler problems. The solutions to some simpler problems may be omitted especially if it does not introduce new ideas.

  1. This is merely an approximation of what a function is doing. ↩

  2. Eventually, by using functions, we will no longer need these conventions. But it is still a useful first step towards the thinking process. ↩