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.

from __init__ import install_dependencies

await install_dependencies()

from ipywidgets import interact
%load_ext divewidgets
%load_ext jupyter_ai
%ai update chatgpt dive:chat

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 chatgpt -f text
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
i = 4
while i <= num:
    print(i)
    i += 1
# Alternative solution
# for i in range(4, num+1):
#     print(i)
### END SOLUTION

How to write code without duplication? One way is to write iterations/loops.^[1]

%%ai chatgpt -f text
In one paragraph, give a concrete example to explain why code duplication is a bad programming practice for carrying out repetitive tasks, and how basic idea of using iteration to avoid code duplication.

Iteration Statements¶

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)

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 chatgpt -f text
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 chatgpt -f text
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)

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 chatgpt -f markdown
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 chatgpt -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)

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

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?

### 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

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

@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])

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

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

@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 interpretor 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

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

%%ai chatgpt -f text
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)

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

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

Is the break statement strictly necessary?

We can use the assignment expression but it is not supported by Python version <3.8.

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)

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

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 num % divisor:
                continue  # where will this go?
            else:
                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 second 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 num % divisor:
                continue
            else:
                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")

In addition to using continue and break in an elegant way, the code also uses 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 = int(num**0.5)  # biggest possible divisor
        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.
↩

Lab 3

Parsing and Validation

Lab 4

Big Number Conversion