Iteration - CS1302

Abstract¶

Iteration is a useful construct that specifies how certain code should be executed repeatedly, thereby avoiding the need for code duplication for repetitive tasks. By leveraging iteration, programmers can streamline their code, making it easier to read and maintain. Readers will learn to write iterations using the while statement, and how unintended infinite loops can be introduced without careful choices of looping/termination conditions. For definitive loops where the number of iterations is known before runtime, readers will learn to write for statements to repeatedly execute a block of code with target variables ranging over some iterable collections of items.

import math
from ipywidgets import interact
%load_ext divewidgets

if not input('Load JupyterAI? [Y/n]').lower()=='n':
    %reload_ext jupyter_ai

Load JupyterAI? [Y/n]

Motivation¶

An important application of programming is to automate the boring stuff:

A significant contributor to boredom is often the repetitive nature of the task. For instance:

Calculating the maximum value of a sequence of numbers, which can be indefinitely long.
Continuously prompting users for input until it meets the validation criteria.
...

%%ai
List three very common repetitive tasks that can be best solved by using 
iteration in programming. Do not include any code.

num = int(input(">"))
if 1 <= num:
    print(1)
if 2 <= num:
    print(2)
if 3 <= num:
    print(3)
### BEGIN SOLUTION
import sys
_ = sys.getrecursionlimit()
sys.setrecursionlimit(max(num+50, _))
def loop_to(n):
    print(n)
    if n<num:
        loop_to(n+1)
loop_to(4)
sys.setrecursionlimit(_)
# Alternative solution 1:
# i = 4
# while i <= num:
#     print(i)
#     i += 1
# Alternative solution 2:
# for i in range(4, num+1):
#     print(i)
### END SOLUTION

Should I reuse code by copy-and-paste?

Code duplication is a bad practice:

Duplicate code is hard to read/write/maintain. Imagine what you need to do to change some code.
The number of repetitions may not be known before runtime, as in Exercise 1.

Instead, a programmer should write a loop/iteration that specifies how a piece of code should be executed repeatedly.

One way to reuse code is to write iterations/loops.^[1]

%%ai
In one paragraph, give a concrete example to explain whether code duplication 
is a good programming practice for carrying out repetitive tasks, and how
iteration may enhance code duplication.

%%ai
Code duplication appears to be more flexible than an iteration because each copy
can be tweaked independently without touching a shared loop.

Loops¶

While Loop¶

We can use the while statement to repeatedly execute certain code until a specified looping condition is false. A simplifed version of the syntax is:

while_stmt ::=  "while" assignment_expression ":" suite

%%flowchart
st=>start: Start
cond1=>condition: assignment_expression
suite1=>operation: suite
e=>end

st(right)->cond1
cond1(yes, right)->suite1(right)->cond1
cond1(no)->e

In other words, suite is repeatedly executed as long as assignment_expression is interpreted as True by the control flow statement.

As an example, the following program keep asking for user input until the input is non-empty.

while not input("Input something please:"):
    pass

If user inputs nothing, input returns an empty string '', which is regarded as False by control flow statements, and so the looping condition not input('...') is True.

Consider the following while loop which attempt to solve Exercise 1:

num = int(input(">"))
i = -1
while i != num:
    i += 1
    print(i)

> 5

Solution to Exercise 2

When the input corresponds to an integer $\leq -2$ , the while loop becomes an infinite loop. The following is a formal proof by induction of a loop invariant:

Indeed, it is impossible to automatically determine whether a program terminates, a challenge known as the Halting problem. See if LLM can summarize the halting problem:

%%ai
Explain the idea of the proof that the halting problem is undecidable.
In particular, explain concisely in two paragraphs using the diagonalization 
argument.

See if LLM can summarize an analogous proof of the diagonalization argument by Cantor on Number Theory.

%%ai
Explain why real numbers are uncountable.
In particular, explain concisely in two paragraphs using the diagonalization 
argument.

For Loop¶

One way to fix the issue in Exercise 2 is to modify the condition of the while loop. (How?) However, we will learn a better fix as follows using the for statement:

for i in range(int(input(">")) + 1):
    print(i)

> -1

A simplified version of the syntax is:

for_stmt ::=  "for" target_list "in" starred_list ":" suite

It is rather difficult to illustrate the execution using a flowchart. See if LLM can summarize the syntax.

%%ai
In one paragraph, explain the syntax of a for loop in Python.

How to print from 0 to 4?

Let us visualize the execution of a simpler version of the for loop that prints from 0 up to 4:

%%optlite -h 300
for i in 1, 2, 3, 4:
    print(i)

i is automatically assigned to each element in the sequence 1, 2, 3, 4 one-by-one from left to right.^[2]
After each assignment, the body print(i) is executed.

Unlike other languages such as C, Python’s for loop uses the in keyword to iterate over a collection of objects called an iterable.

%%ai -f markdown
Write a for loop in C to print numbers from 1 to 4.

One benefit of using iterable is that it is difficult to write an infinite loop using the Python for loop.^[3] Another reason is that this allows Python to be more expressive and easy to read. For instance:

tuples = (0, "l"), (1, "o"), (2, "o"), (3, "p")
for i, c in tuples:
    print(i, c)

0 l
1 o
2 o
3 p

for i, c in enumerate("loop"):
    print(i, c)

0 l
1 o
2 o
3 p

How to print up to a user-specified number?

The complete fix to Exercise 2 uses range:

stop = int(input(">")) + 1
for i in range(stop):
    print(i)

Why add 1 to the user input number?

range(stop) generates a sequence of integers from 0 up to but excluding stop:

1
2
3
4
5
6
7
8
9
10
Init signature: range(self, /, *args, **kwargs)
Docstring:     
range(stop) -> range object
range(start, stop[, step]) -> range object

Return an object that produces a sequence of integers from start (inclusive)
to stop (exclusive) by step.  range(i, j) produces i, i+1, i+2, ..., j-1.
start defaults to 0, and stop is omitted!  range(4) produces 0, 1, 2, 3.
These are exactly the valid indices for a list of 4 elements.
When step is given, it specifies the increment (or decrement).

How to start from a number different from 0?

We can use two arguments to specify the start and stop.

for i in range(1, 5):
    print(i)

What about a step size different from 1?

We can use an additional step argument.

for i in range(0, 5, 2):
    print(i)  # starting number must also be specified. Why?

0
2
4

### BEGIN SOLUTION
for i in range(4, -1, -1):
    print(i)
### END SOLUTION

Exercise 4 (fractional steps)

Print from 0 to a user-specified number but in steps of 0.5.
E.g., if the user inputs 2, the program should print:

0.0
0.5
1.0
1.5
2.0

Caution

range only accepts integer arguments, so range(0, 2, 0.5) is invalid because 0.5 is not an integer.

num = int(input(">"))
### BEGIN SOLUTION
for i in range(0, 2 * num + 1, 1):
    print(i / 2)
### END SOLUTION

> 5

0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0

@interact(m=(0, 10), n=(0, 10))
def draw_rectangle(m=5, n=5):
    ### BEGIN SOLUTION
    for i in range(m):
        for j in range(n):
            print("*", end="")
        print()
    # Alternative solution: print(m * ("*" * n + "\n"))
    ### END SOLUTION

What about iterating over characters of a string?

%%optlite -h 300
for character in "loop":
    print(character)

In Python, str is also regarded as an iterable, or more specifically, a sequence type, namely, a sequence of characters.

The function len can return the length of a string.
The indexing operator [] can return the character of a string at a specified location.

message = "loop"
print("length:", len(message))
print("characters:", message[0], message[1], message[2], message[3])
# Negative indexing also allowed.
print("characters:", message[-4], message[-3], message[-2], message[-1])

length: 4
characters: l o o p
characters: l o o p

We can also iterate over a string as follows although it is less elegant:

for i in range(len("loop")):
    print("loop"[i])

l
o
o
p

@interact(message="loop")
def reverse_print(message):
    ### BEGIN SOLUTION
    for i in range(len(message)):
        print(message[-i - 1], end="")
    print("")  # final line break
    # Alternative solution
    # print(message[::-1])
    ### END SOLUTION

While Loop vs For Loop¶

How to decide whether to use while loop or for loop?

It is always possible to replace a for loop by a while loop. Indeed, a for loop such as

for i in range(5): print(i)

translates to the following code using a while loop:

%%optlite -h 400
iterable = range(5)
iterator = iter(iterable)
try:
    while True:
        i = next(iterator)
        print(i)
except StopIteration: pass

When executing the for loop,

the interpreter creates an iterator from the iterable, which tracks the next element to be assigned to the target variable.^[4]
The loop terminates automatically when the iterator has no next element and raises an exception to signal the end of iteration.^[5]

We can compare the speed of the for loop and while loop using the cell magic %%timeit as follows:

%%timeit
for i in range(5): cur_count = i

118 ns ± 0.0607 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%%timeit
i = 0
while i < 5:
    cur_count = i
    i += 1

130 ns ± 0.241 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%%ai
Is it always possible to replace a while loop by a for loop?

Break/Continue/Else Constructs¶

So far, we have ignored part of the syntax of the for loop and while loop:

while_stmt ::=  "while" assignment_expression ":" suite
                ["else" ":" suite]

for_stmt   ::=  "for" target_list "in" starred_list ":" suite
                ["else" ":" suite]

namely, the else clause ["else" ":" suite] which also appears in the if statement. How does it work?

Breaking out of a loop¶

Is the following an infinite loop?

while True:
    message = input("Input something please:")
    if message:
        break
print("You entered:", message)

Input something please: 
Input something please: 
Input something please: 123

You entered: 123

The loop is terminated by the break statement when user input is non-empty.

Why is the break statement useful?

Recall the earlier while loop:

while not input("Input something please:"):
    pass

Input something please: 123

This while loop is not useful because it does not store the user input.

Is the break statement strictly necessary?

No, as we can use assignment expressions starting with Python version 3.8.

More generally, we can avoid break statement by using flags, which are boolean variables for flow control:

has_no_input = True
while has_no_input:
    message = input("Input something please:")
    if message:
        has_no_input = False
print("You entered:", message)

Input something please: 
Input something please: 123

You entered: 123

Continue to Next Iteration¶

What does the following program do?
Is it an infinite loop?

while True:
    message = input("Input something please:")
    if not message:
        continue
    print("You entered:", message)

The program repeatedly asks the user for input.
If the input is empty, the continue statement will skip to the next iteration.
The loop can only be terminated by interrupting the kernel.
Such an infinite loop can be useful. E.g., your computer clock continuously updates the current time.

while True:
    message = input("Input something please:")
    ### BEGIN SOLUTION
    if message:
        print("You entered:", message)
    ### END SOLUTION

Input something please: 
Input something please: 
Input something please: 123

You entered: 123

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
Cell In[37], line 2
      1 while True:
----> 2     message = input("Input something please:")
      3     ### BEGIN SOLUTION
      4     if message:

File /opt/conda/lib/python3.12/site-packages/ipykernel/kernelbase.py:1282, in Kernel.raw_input(self, prompt)
   1280     msg = "raw_input was called, but this frontend does not support input requests."
   1281     raise StdinNotImplementedError(msg)
-> 1282 return self._input_request(
   1283     str(prompt),
   1284     self._parent_ident["shell"],
   1285     self.get_parent("shell"),
   1286     password=False,
   1287 )

File /opt/conda/lib/python3.12/site-packages/ipykernel/kernelbase.py:1325, in Kernel._input_request(self, prompt, ident, parent, password)
   1322 except KeyboardInterrupt:
   1323     # re-raise KeyboardInterrupt, to truncate traceback
   1324     msg = "Interrupted by user"
-> 1325     raise KeyboardInterrupt(msg) from None
   1326 except Exception:
   1327     self.log.warning("Invalid Message:", exc_info=True)

KeyboardInterrupt: Interrupted by user

Else construct for a loop¶

The following program checks whether a number is composite, namely,

a positive integer that is
a product of two strictly smaller positive integers.

@interact(num="1")
def check_composite(num):
    if num.isdigit():
        num = int(num)
        for divisor in range(2, num):  # why starts from 2 instead of 1
            if not num % divisor:
                print("It is composite.")
                break  # where will this go?
        else:
            print("It is not composite.")  # how to get here?
    else:
        print("Not a positive integer.")  # how to get here?

Solution to Exercise 8

The first else clause that print('It is not composite.').
The clause is called when there is no divisor found in the range from 2 to num.

Try stepping through execution to understand the flow of the program:

%%optlite -h 650
def check_composite(num):
    if num.isdigit():
        num = int(num)
        for divisor in range(2, num):
            if not num % divisor:
                print("It is composite.")
                break
        else:
            print("It is not composite.")
    else:
        print("Not a positive integer.")


check_composite("1")
check_composite("2")
check_composite("3")
check_composite("4")

The for loop has an else clause that is executed only when the loop terminates normally, i.e., not by a break.

@interact(num="1")
def check_composite(num):
    if num.isdigit():
        num = int(num)
        ### BEGIN SOLUTION
        # for divisor in range(2,num):
        divisor = math.isqrt(num) # int(num**0.5) would not work
        while divisor > 1:
            if num % divisor:
                divisor -= 1  # why not go from 2 to int(num ** 0.5)?
            else:
                print("It is composite.")
                break
        else:
            print("It is not composite.")
        ### END SOLUTION
    else:
        print("Not a positive integer.")

Footnotes¶

Another way you will learn later in the course is to write functions and recursions.
↩
If i is defined before the for loop, its value will be overwritten.
↩
As a challenge, can you rewrite the infinite loop while True: pass as a for loop? You will learn later in the course that this is possible if you so desire!
↩
The iter function is used to create an iterator from an iterable, such as a range object. Each iteration of the while loop calls the next function on the iterator to retrieve the next value from the iterable.
↩
If there are no more next values, the iterator raises a StopIteration exception. The except block is used to catch this exception to prevent it from bubbling up further and crashing the program. The try block specifies the code to monitor for the exception to catch.
↩