Skip to content

Iteration Statement

Learning Objectives

At the end of this sub-unit, students should

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

Repeating a Task

We will look at a problem that is simple to state but we currently cannot solve yet. This is the prototypical problem of iteration of computing the factorial of a number \(n\) (denoted as \(n!\)). This does not mean that we have to shout the number. The definition of a factorial is shown below and we will limit our problem to a non-negative \(n\) (i.e., \(n \geq 0\)).

\[ n! = n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1 \]

We also need to define separately, that \(0! = 1\). This is because we end with \(\times 1\) and we cannot extend this to \(\times 0\) because then the result will always be \(0\). So \(0! = 1\) is by definition.

In solving this problem, we will find that for any particular value of \(n\), we can write an expression that correspond to the factorial of that value. The expressions for some values of \(n\) are given below. Unfortunately, extending this to an arbitrary value of non-negative \(n\) is difficult because the \(\cdots\) is doing the heavy lifting of the operations here. We can see the problem by looking at the code below and notice that each solution has different expressions.

\[ k^n = k \times k \times \cdots \times k \times k \ \ \ \ \ \ \ (n - 1 \ \text{operations of} \ \times)\]
1
2
3
fact4 = 4 * 3 * 2 * 1                            # 4!
fact5 = 5 * 4 * 3 * 2 * 1                        # 5!
fact10 = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1  # 10!

Before we try to solve factorial, let us look at an even simpler problem that will highlight the need for repetition. This problem is the exponentiation problem. For now, simply forget that Python has the ** operator. Instead, can we implement exponentiation as a repeated multiplication (i.e., repeated *).

1
2
expk_4 = k * k * k * k      # k ** 4
expk_5 = k * k * k * k * k  # k ** 5

As the last two examples show, we need to repeat the multiplication for \(n - 1\) times to compute \(k^n\) if we count the number of * in the code. So we need to be able to repeat the operation * k for some arbitrary number of times that depends on another value \(n\). How do we do this?

While-Loop

The construct we need is called an iteration statement. Note that there are two different kinds of iteration statement. However, we will only discuss one of them here which is the while-loop. The other one --called the for-loop-- will be introduced when it can be used to simplify some aspect of computations. In particular, we will introduce for-loop in our discussion of sequence.

Quote

"I fear not the man who has practiced 10,000 kicks once, but I fear the man who has practiced one kick 10,000 times."

Bruce Lee

Syntax

We will use the notation we used for if-statement here. The explanation is given below.

1
2
while ❬ expression ❭ :
  ❬ block ❭
  • It must start with the while keyword.
    • The while keyword is followed by a condition (i.e., boolean expression).
    • This line is terminated by a colon (i.e., :).
    • The next line is an inner block called the loop body.

Recap the colon rule.

Colon Rule

"After every colon (i.e., :), the next line should be more indented."

Also recap the converse rule.

"Consider an indented line, there must be a line with fewer indentation that ends with a colon (i.e., :)"

As usual, we also need to discuss the semantics. We will still be using the informal explanation as well as the flowchart for the semantics.

Semantics

1
2
while cond:
  body
  1. Evaluate the boolean expression cond into a value \(V\).
  2. If \(V\) is False, then go to Step 5. Otherwise go to Step 3.
  3. Evaluate the block body.
    • This may modify the value used in cond.
  4. Go back to Step 1.
  5. End of loop.

Note that the "loop" part is conveyed by Step 4 as it goes back to Step 1. To "exit" this loop, the condition cond must evaluate to False. We will often call cond as the loop-condition.

While01

Exponentiation

With this, we can now solve the exponentiation problem before solving the more complicated factorial. Although we can short-circuit this entire explanation simply as the following

Repeat * k for exactly n - 1 times

we will be explaining the steps more slowly especially if this is your first time encountering while-loop.

The basic idea can be captured as follows. If we look at the semantics of while-loop above, we can ask ourselves "how many times will body will be executed?" The answer is "while cond evaluates to True". So it can be 0, 1, 2, or even 5 times. Now if we look at what the code looks like without the while-loop, we will see the following. If we extending it to an arbitrary \(n\), we get something resembling the last tab, which approaches the \(\cdots\), but vertical.

1
2
# before loop
# after loop

1
2
3
# before loop
body
# after loop

1
2
3
4
# before loop
body
body
# after loop

1
2
3
4
5
6
7
# before loop
body
body
body
body
body
# after loop

1
2
3
4
5
6
7
# before loop
body
body
  :   # repeat until a total of n body
body
body
# after loop

So here is the idea:

Can we make the code for exponentiation (i.e., \(k^n\)) look identical vertically?

Let us explore this idea using a fixed value. This is a good technique to use. If a problem is too complicated, can we simplifying by fixing some values. So let us consider only \(3^4\). As a single line, it is trivial, even if we do not have the exponentiation operation (i.e., no 3 ** 4).

1
res = 3 * 3 * 3 * 3

But this is a single line. We need a code that potentially has several lines but we want the code to be identical vertically. There are two exceptions to this identical rule.

  • We can have the first line be different (i.e., # before loop).
  • We can have the last line be different (i.e., # after loop).

So let us try to rewrite this single line into multiple lines. If we are allowed to have first or last line be different, we actually have several possibilities because we are also allowed to have both be different. But let us restrict this to just be either the first or last line.

1
2
3
4
res = 3
          * 3
          * 3
          * 3

1
2
3
4
res = 3 *
      3 *
      3 *
      3

The "Before Loop" version looks more promising as Line 2 to Line 4 are really identical. However, Line 2 to Line 4 are not valid code. But if we look only at the idea, we will see that the idea is to compute the following.

1
2
3
4
res = 3        # 3
          * 3  # 3 * 3
          * 3  # 3 * 3 * 3
          * 3  # 3 * 3 * 3 * 3

If we collapse the computations before the last * 3 into a value, we get the following even more similar computation.

1
2
3
4
res = 3        # 3
          * 3  # 3  * 3 = 9
          * 3  # 9  * 3 = 27
          * 3  # 27 * 3 = 81

Now we can see some connections between the lines. The value 9 at Line 3 (i.e., 9 * 3) comes from Line 2 (i.e., 3 * 3 = 9). This connection also extends to Line 4. If we can also imagine \(3^5\), it will also extends to an imaginary Line 5. So we are on good path here. What we need now is to actually connect these lines. Let's do this in a naïve way first before making it identical by using multiple variables to store the result from previous line.

1
2
3
4
res = 3        # 3
v1  = res * 3  # 3  * 3 = 9
v2  = v1  * 3  # 9  * 3 = 27
v3  = v2  * 3  # 27 * 3 = 81

We then note that we only need one variable. This variable is in fact, the variable res.

1
2
3
4
res = 3        # 3
res = res * 3  # 3  * 3 = 9
res = res * 3  # 9  * 3 = 27
res = res * 3  # 27 * 3 = 81

This looks great, Line 2 to Line 4 are now indentical. We can then collapse this into a single line and wrap it inside a while-loop.

1
2
3
4
res = 3 # before loop
while cond:
  res = res * 3
# after loop

The last step is to think about the condition cond. This requires some thinking. At this point, we may want to generalize one of the values we have fixed. So let us generalize \(3^4\) into \(3^n\). Our first guess should be that the condition must involve n and we will be correct. But how do we use it?

Since we have to repeat res = res * 3 for \(n - 1\) times, we can imagine that we have a variable called ctx1 that counts how many times we have performed res = res * 3. Assuming that this variable ctx is updated correctly, the condition simply checks that its value is still less than n - 1.

1
2
3
4
res = 3 # before loop
while ctx < n - 1: # assume n is initialized
  res = res * 3
# after loop

We now have two problems.

  1. What is the initial value of ctx?
  2. How do we update ctx?

With a little bit of thinking, we should arrive at the following solution.

1
2
3
4
5
6
res = 3 # before loop
ctx = 0 # initial ctx
while ctx < n - 1: # assume n is initialized
  res = res * 3
  ctx = ctx + 1 # update ctx
# after loop

Now we are ready to fully generalize \(3^n\) into the most general form \(k^n\). This gives us the following code.

1
2
3
4
5
6
7
# Assume k and n are initialized
res = k
ctx = 0
while ctx < n - 1:
  res = res * k
  ctx = ctx + 1
print(res)

Before we solve factorial, let us first analyze our solution and see if we can improve this. We start by asking ourselves what our assumptions are when we write the code. Here are some example of potential questions to ask.

  • Do we assume n > 0?
    • Should we allow n == 0?
    • Should we allow n < 0?
  • Do we assume k > 0?
    • Should we allow k == 0?
    • Should we allow k < 0?

For now, let us assume that k can be any number. As for n, let us assume that n can be 0. Does our code work with this assumption? A little check reveals that if we set k = 3 and n = 0, the output we get is 3. However, the answer should be 1. So there must be a mistake.

Our job now is to narrow down the possible lines where mistakes may happen. If we try to trace the execution of the loop slowly, this result comes because we initialize res = k. Then, at the start of the loop, the loop-condition becomes 0 < 0 - 1 which is False. So the initial value of res should not be k. Instead, we should have gotten 1 as the output and this is the value we should start with.

Exponentiation

1
2
3
4
5
6
7
# Assume k and n are initialized
res = 1
ctx = 0
while ctx < n - 1:
  res = res * k
  ctx = ctx + 1
print(res)

Factorial

Now we are ready to tackle the factorial problem. To avoid the entire long explanation again, we will compress the steps into tabs with each tab corresponding to the transformation we did above for exponentiation. We start with a fix value of \(4!\). Try to attempt the above step by step before looking at how we are doing it.

1
res = 4 * 3 * 2 * 1

1
2
3
4
res = 4
          * 3  # 4 * 3         = 4  * 3
          * 2  # 4 * 3 * 2     = 12 * 2
          * 1  # 4 * 3 * 2 * 1 = 24 * 1

1
2
3
4
res = 4
v1  = res * 3  # 4 * 3         = 4  * 3
v2  = v1  * 2  # 4 * 3 * 2     = 12 * 2
v3  = v2  * 1  # 4 * 3 * 2 * 1 = 24 * 1

1
2
3
4
res = 4
res = res * 3  # 4 * 3         = 4  * 3
res = res * 2  # 4 * 3 * 2     = 12 * 2
res = res * 1  # 4 * 3 * 2 * 1 = 24 * 1

Now, at this point, we are somewhat stuck. It looks quite close but we have different operands as our right-hand side. How can we make this identical? We can borrow the idea of the ctx from before. Let us say that there is a variable called val as our operand for the multiplication. Then, the remaining problem we have is how do we connect this? In other words, how do we update val?

1
2
3
4
5
6
7
8
res = 4
# initial val
res = res * val  # val = 3
# update val
res = res * val  # val = 2
# update val
res = res * val  # val = 1
# update val

1
2
3
4
5
6
7
8
res = 4
# initial val
res = res * val  # val = 3
val = val - 1
res = res * val  # val = 2
val = val - 1
res = res * val  # val = 1
val = val - 1

1
2
3
4
5
6
7
8
res = 4
val = 3
res = res * val  # val = 3
val = val - 1
res = res * val  # val = 2
val = val - 1
res = res * val  # val = 1
val = val - 1

1
2
3
4
5
res = 4
val = 3
while cond:
  res = res * val
  val = val - 1

Then, we can do the same trick as we did before. We can count how many times we have the loop-body. However, there is a simpler condition. Notice that we should not multiply by 0. In other words, we should not let val be 0. So the condition is really val > 0 as we want to continue while the value of val is not 0.

1
2
3
4
5
res = 4
val = 3
while val > 0:
  res = res * val
  val = val - 1

Finally, we generalize this to an arbitrary n. Since we fixed n to be 4, we get the following code for factorial.

Factorial

1
2
3
4
5
6
7
# Assume n is initialized
res = n
val = n - 1
while val > 0:
  res = res * val
  val = val - 1
print(res)

  1. ctx is a common name for a counter. ↩