8. More About Iteration

  • Computers are often used to automate repetitive tasks.

  • Repeated execution of a sequence of statements is called iteration.

  • for and while statement

The for loop revisited

for f in ["Joe", "Amy", "Brad", "Angelina"]:
    print("Hi", f, "Please come to my party on Saturday")
In [ ]:
def sumTo(aBound):
    theSum = 0
    for aNumber in range(1, aBound + 1):
        theSum = theSum + aNumber

    return theSum

print(sumTo(4))

print(sumTo(1000))
In [ ]:
print(sum(range(4+1)))

print(sum(range(1000+1)))

The while Statement

In [ ]:
def sumTo(aBound):
    """ Return the sum of 1+2+3 ... n """
    theSum  = 0
    aNumber = 1
    while aNumber <= aBound:
        theSum = theSum + aNumber
        aNumber = aNumber + 1
    return theSum

print(sumTo(4))
print(sumTo(1000))
In [1]:
from IPython.display import IFrame
IFrame('http://pythontutor.com/iframe-embed.html#code=def%20sumTo(aBound%29%3A%0A%20%20%20%20%22%22%22%20Return%20the%20sum%20of%201%2B2%2B3%20...%20n%20%22%22%22%0A%0A%20%20%20%20theSum%20%20%3D%200%0A%20%20%20%20aNumber%20%3D%201%0A%20%20%20%20while%20aNumber%20%3C%3D%20aBound%3A%0A%20%20%20%20%20%20%20%20theSum%20%3D%20theSum%20%2B%20aNumber%0A%20%20%20%20%20%20%20%20aNumber%20%3D%20aNumber%20%2B%201%0A%20%20%20%20return%20theSum%0A%0Aprint(sumTo(4%29%29%0A%0Aprint(sumTo(100%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width='100%', height=450)
Out[1]:

Definite iteration vs Indefinite iteration

Definite iteration

Usually a for loop creates a definite iteration because we definitely know how many times we are going to iterate.

Indefinite iteration

The while statement is dependent on a condition that needs to evaluate to False in order for the loop to terminate. Since we do not necessarily know when this will happen, it creates what we call indefinite iteration.

Exercise

True or False: You can rewrite any for-loop as a while-loop.
(A) True
(B) False

Randomly Walking Turtles

A walking turtle and program to behave in the following way:

  • The turtle begins in the center of the screen.
  • Flip a coin. If its heads then turn to the left 90 degrees. If its tails then turn to the right 90 degrees.
  • Take 50 steps forward.
  • If the turtle has moved outside the screen then stop, otherwise go back to step 2 and repeat.
create a window and a turtle

while the turtle is still in the window:
    generate a random number between 0 and 1
    if the number == 0 (heads):
        turn left
    else:
        turn right
    move the turtle forward 50
In [ ]:
import random
import turtle

def isInScreen(w, t):
    return True

t = turtle.Turtle()
wn = turtle.Screen()

while isInScreen(wn, t):
    if (random.randrange(0, 2) == 0):
        t.left(90)
    else:          # tails
        t.right(90)
    t.forward(50)

Exercise

Which type of loop can be used to perform the following iteration: You choose a positive integer at random and then print the numbers from 1 up to and including the selected integer.
(A) a for-loop or a while-loop
(B) only a for-loop
(C) only a while-loop

The 3n + 1 Sequence

The Collatz conjecture

$$ f(n) = \begin{cases} n/2, & \text{if $n$ is even} \\ 3n+1, & \text{if $n$ is odd} \end{cases} $$$$ a_{i}={\begin{cases}n&{\text{for }}i=0\\f(a_{i-1})&{\text{for }}i>0\end{cases}} $$

This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

In [ ]:
def seq3np1(n):
    """ Print the 3n+1 sequence from n, terminating when it reaches 1."""
    while n != 1:
        print(n)
        if n % 2 == 0:        # n is even
            n = n // 2
        else:                 # n is odd
            n = n * 3 + 1
    print(n)                  # the last print is 1

seq3np1(6171)
seq3np1(63728127)

Newton’s Method: computing square roots

$$f(x)=x^2 - a$$$$ x:f(x)=0 $$\begin{align} x_{1} & = x_{0}-{\frac {f(x_{0})}{f'(x_{0})}} \\ & = \frac{x_0}{2}+\frac{a}{2x_0} \end{align}
In [ ]:
import random
def newtonSqrt(n, howmany):
    approx = 0.5 * n
    for i in range(howmany):
        betterapprox = 0.5 * (approx + n/approx)
        approx = betterapprox
    return betterapprox

print(10**0.5)
print(newtonSqrt(10, 3))
print(newtonSqrt(10, 5))
print(newtonSqrt(10, 10))
In [ ]:
def newtonSqrt(n):
    approx = 0.5 * n
    better = 0.5 * (approx + n/approx)
    while better != approx:
        approx = better
        better = 0.5 * (approx + n/approx)
    return approx

print(newtonSqrt(10))
In [2]:
from IPython.display import IFrame
IFrame('http://pythontutor.com/iframe-embed.html#code=def%20newtonSqrt(n%29%3A%0A%20%20%20%20approx%20%3D%200.5%20*%20n%0A%20%20%20%20better%20%3D%200.5%20*%20(approx%20%2B%20n/approx%29%0A%20%20%20%20while%20better%20!%3D%20approx%3A%0A%20%20%20%20%20%20%20%20approx%20%3D%20better%0A%20%20%20%20%20%20%20%20better%20%3D%200.5%20*%20(approx%20%2B%20n/approx%29%0A%20%20%20%20return%20approx%0A%0Aprint(newtonSqrt(10%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width='100%', height=400)
Out[2]:

floating point numbers comparition

while better != approx:

how to improve?

Simple Tables

In [ ]:
print("n", '\t', "2**n")     #table column headings
print("---", '\t', "-----")

for x in range(13):        # generate values for columns
    print(x, '\t', 2 ** x)

Exercise

What is the difference between a tab ('\t') and a sequence of spaces?
(A) A tab will line up items in a second column, regardless of how many characters were in the first column, while spaces will not.
(B) There is no difference
(C) A tab is wider than a sequence of spaces
(D) You must use tabs for creating tables. You cannot use spaces.

Nested Iteration

In [ ]:
for i in range(5):
    for j in range(3):
        print(i, j)
In [3]:
from IPython.display import IFrame
IFrame('http://pythontutor.com/iframe-embed.html#code=for%20i%20in%20range(5%29%3A%0A%20%20%20%20for%20j%20in%20range(3%29%3A%0A%20%20%20%20%20%20%20%20print(i,%20j%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width='100%', height=400)
Out[3]:

the break statement

The break statement is used to immediately leave the body of its loop.

The next statement to be executed is the first one after the body.

In [ ]:
for i in [12, 16, 17, 24, 29]:
    if i % 2 == 1:  # If the number is odd
       break        #  ... immediately exit the loop
    print(i)
print("done")

middle-test loop

In [ ]:
total = 0
while True:
    response = input("Enter the next number. (Leave blank to end)")
    if response == "":
        break
    total += int(response)
print("The total of the numbers you entered is ", total)

post-test loop

while True:
    play_the_game_once()
    response = input("Play again? (yes or no)")
    if response != "yes":
        break
print("Goodbye!")
In [ ]:
import random                   # We cover random numbers in the
rng = random.Random()           #  modules chapter, so peek ahead.
number = rng.randrange(1, 1000) # Get random number between [1 and 1000).
guesses = 0
msg = ""
while True:
    guess = int(input(msg + "\nGuess my number between 1 and 1000: "))
    guesses += 1
    if guess > number:
        msg += str(guess) + " is too high.\n"
    elif guess < number:
        msg += str(guess) + " is too low.\n"
    else:
        break
print("\n\nGreat, you got it in {0} guesses!\n\n".format(guesses))

The continue statement

This is a control flow statement that causes the program to immediately skip the processing of the rest of the body of the loop, for the current iteration.

But the loop still carries on running for its remaining iterations.

In [ ]:
for i in [12, 16, 17, 24, 29, 30]:
    if i % 2 == 1:      # If the number is odd
       continue         # Don't process it
    print(i)
print("done")

Exercise

1. Is the interger prime?

2. Greatest common divisor(gcd) problem

3. Fibonacci sequence

4. Print the 99 multiplication table

Glossary

algorithm

A step-by-step process for solving a category of problems.

body

The statements inside a loop.

counter

A variable used to count something, usually initialized to zero and incremented in the body of a loop.

cursor

An invisible marker that keeps track of where the next character will be printed.

definite iteration

A loop where we have an upper bound on the number of times the body will be executed. Definite iteration is usually best coded as a for loop.

escape sequence

An escape character, \\, followed by one or more printable characters used to designate a nonprintable character.

generalize

To replace something unnecessarily specific (like a constant value) with something appropriately general (like a variable or parameter). Generalization makes code more versatile, more likely to be reused, and sometimes even easier to write.

infinite loop

A loop in which the terminating condition is never satisfied.

indefinite iteration

A loop where we just need to keep going until some condition is met. A while statement is used for this case.

iteration

Repeated execution of a set of programming statements.

loop

A statement or group of statements that execute repeatedly until a terminating condition is satisfied.

loop variable

A variable used as part of the terminating condition of a loop.

nested loop

A loop inside the body of another loop.

newline

A special character that causes the cursor to move to the beginning of the next line.

reassignment

Making more than one assignment to the same variable during the execution of a program.

tab

A special character that causes the cursor to move to the next tab stop on the current line.