0% found this document useful (0 votes)
12 views18 pages

Python Iteration and Loop Structures

The document discusses iterative structures in Python, comparing recursion and iteration through examples like countdown functions and primality testing. It explains the mechanics of while and for loops, including their initialization, continuation tests, and variable updates. Additionally, it highlights the advantages of iteration over recursion in terms of memory efficiency and speed.

Uploaded by

createthread
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
12 views18 pages

Python Iteration and Loop Structures

The document discusses iterative structures in Python, comparing recursion and iteration through examples like countdown functions and primality testing. It explains the mechanics of while and for loops, including their initialization, continuation tests, and variable updates. Additionally, it highlights the advantages of iteration over recursion in terms of memory efficiency and speed.

Uploaded by

createthread
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Iterative structure in Python

In Python, repetition can be recursive


def count_down_rec(x):
‘’’ Produces the list
[x, x - 1, x - 2, ..., 1,0]
count_down: Nat -> (listof Nat)
‘’’
if x == 0:
return [0]
else:
return [x] + count_down(x-1)
But it can be different  Iteration
def count_down(x):
answer = []
while x >= 0:
[Link](x)
x=x–1
return answer

What happens when we call count_down(3)?


while loop basics
• If the continuation test is True,
• Execute the loop body
• If the continuation test is False,
• Do not execute the loop body
• After completing the loop body:
• Evaluate the continuation test again
• The body usually includes an update of variables used in the
continuation test
while loop template
## initialize loop variables
while test:
## body, including statements to:
## 1) update variables used in test
## 2) update value being calculated
Steps for writing a while loop
• You must determine
• how to initialize variables outside the loop
• when the loop body should be executed, or, when it should stop
• what variables must be updated in the loop body so the loop will eventually
stop
• what other actions are needed within the loop body
Example: Checking Primality
• A number n >= 2 is prime if it has no factors other than 1 and itself.

• To test if a number n is prime:


• Check every number from 2 to n-1
• If you find a factor of n, stop and return False
• If none of them are, stop and return True
• Determine what steps should be in side the loop, and which should be
outside
Implementation of is_prime
def is_prime (n):
‘’’ is_prime: Nat -> Bool
Requires: n >= 2
‘’’
test_factor = 2
while test_factor < n:
if n % test_factor == 0:
return False
else:
test_factor = test_factor + 1
return True
Beware of “infinite loops”
while True: x = -5
print('runs forever') total = 0
while x < 0:
total += 2.0 ** x
x -= 1
print(total)
Exercise: factorial
• Write a Python function to calculate n!
• Use a while loop that counts from 1 to n
• Use a while loop that counts down from n to 1
Why use loops instead of recursion?
• Iteration may allow for a more “natural” solution
• Python won’t let us do recursion thousands of times
• Iteration is more memory efficient
• for each recursive call, we need memory for parameters
• for an iterative call, we may just need to update an existing variable
• Iteration will generally run faster
Another type of loop: for
• While loops are called guarded iteration:
• If the test evaluates to True, execute the body

• Another approach:
• Iterate over all members in a collection
• Called bounded iteration

for item in collection:


loop_body
for loop examples
for food in ['avocado', 'banana', 'cabbage’]:
print([Link]())

for base in 'ACGGGTCG’:


print(base)
for loop examples using range
sum_all = 0
for i in range(2, 5):
sq = i * i
sum_all = sum_all + sq
print(sum_all)

for j in range(10, 2, 2):


print(j)

• range is used to generate a collection of integers


• The next value in the range is computed automatically with each pass through the for loop.
for and while

while for
• Loop counter should be • Loop counter initialized
initialized outside loop automatically
• Includes continuation test • Continues while more elements in
before body the collection
• Should update loop variables • Loop variable updated automatically
in body of loop – do not update in loop
• Body contains steps to repeat • Body contains steps to repeat
What does this function do?
def smaller(L, x): • How many iterations would
p=0 smaller([10, 8, 6], 3) involve?
while p < len(L):
if L[p] < x: • smaller([7, 10, 2], 8)?
return p
else: • smaller(L, x) for any L and x?
p = p+1
return False
What does this function do?
def mult_table(n):
table = []
for r in range(n):
row = []
for c in range(n):
[Link](r*c)
[Link](row)
return table

• How many total iterations would mult_table(5) involve?


• mult_table(n) for any Nat n?

Common questions

Powered by AI

A 'for' loop in Python automatically initializes and updates the loop variable while iterating over a collection, so manual updates are not required. In contrast, a 'while' loop requires manual initialization, condition-checking, and updating of the loop variable within the loop body .

For mult_table(n) with n=5, the total number of iterations is 25. This is calculated by the nest of two loops with the range n; specifically, the outer loop runs n times (here, 5 times), and for each iteration of the outer loop, the inner loop runs n times, leading to n*n, which is 5*5=25 iterations total .

Guarded iteration refers to the process where the loop body is executed only if a specific condition, the guard, evaluates to True. In 'while' loops, this means the loop continues to execute its body as long as the continuation condition remains true, checking the condition before each iteration .

An iterative approach using a 'while' loop for counting down initializes a list and appends each number within the loop until the condition fails, while the recursive approach calls the function itself with the decreased value until reaching the base case. The iterative method typically uses less memory and is often more efficient because it avoids the overhead associated with recursive function calls .

The is_prime function checks each number up to n-1 to determine if the input number has any divisors, executing a division operation for each potential factor, which can be slow for large numbers. In contrast, the count_down function simply decrements and appends numbers in a list without complex calculations, generally resulting in faster execution even with large numbers due to its simpler operations .

In 'for' loops, the loop variable is automatically set and updated as it iterates over each element in a sequence or range, with no manual intervention. In contrast, 'while' loops require the loop variable to be manually initialized and updated within the loop body, which gives greater control but also necessitates caution to prevent errors such as infinite loops .

When using Python's 'range' function within loops, potential issues include oversized memory usage if the range is very large or off-by-one errors if the bounds are misunderstood. Mitigating these issues involves carefully choosing the start, stop, and step values, and using generator expressions or libraries like NumPy for handling large data sets .

Iteration may be preferred over recursion in Python for large computations because it is generally more memory efficient and faster. Each recursive call requires additional memory for parameters, whereas iterative calls usually just update existing variables. Additionally, Python has a recursion depth limit, making iteration more practical for deeply nested operations .

When designing a 'while' loop, it is crucial to properly initialize loop variables, incorporate a continuation condition that will eventually become false, and update loop variables within the body so the loop progresses toward its condition being false. Failing to do any of these may lead to an infinite loop .

An improper test condition in a 'while' loop can lead to unintended infinite loops or premature termination. For instance, if the continuation test incorrectly checks 'x > 0' instead of 'x >= 0' when counting down to zero, the loop will miss processing the value zero, leading to incorrect outcomes. Correct test conditions must reflect the exact intended stopping criteria to prevent such logical errors .

You might also like