Iteration

From CS 61A Wiki
Revision as of 13:25, 12 June 2014 by Axis (Talk | contribs)


Jump to: navigation, search

Iteration is the process of repeatedly executing a block of code. The ability to execute a segment of code multiple times is necessary in complex programs. It helps minimize copying and pasting code — instead of writing the same lines of code over and over again, we can simply put those lines inside a loop. Almost every programming language (including Python) offers ways to loop over a part of code.

The while statement

The simplest form of iteration is the while statement. A while statement consists of a condition and a suite of statements:

while condition:
    # suite

A while statement executes its suite as long as condition evaluates to a True value. condition is checked each time before executing the suite again. If condition evaluates to a False value, execution continues with the statements after the while loop.

If the suite does not modify the variables being tested in the header expression, the loop will run forever. This is called an infinite loop. In the Python interpreter, press <Control>-C to terminate the program.

Simple example

The following while loop prints the numbers 0 – 10:

>>> i = 0
>>> while i <= 10:
...     print(i)
...     i += 1
... 
0
1
2
3
4
5
6
7
8
9
10

Example: First 10 Fibonacci numbers

Let's assume that one day Rohin wanted to challenge Andrew; so he asks Andrew to find a way to write out first 10 fibonacci numbers.

The Fibonacci sequence is a mathematical sequence whose first two numbers are 1 and 1, and the next of the numbers in the sequence are obtained by adding previous two numbers. If he starts with first two values of fibonacci sequence he can add those two numbers to create the third number and then add the 3rd and 2nd number to create the 4th and then 4th and 3rd to create the 5th and so forth. He realizes that Rohin gave Andrew an iterative process and he can use a while statement. He writes:

i = 10
previous = 0
current = 1
while i > 0:
    previous, current = current, previous + current
    i = i - 1    print(previous)

Remember in the assignment previous, current = current, previous + current the key thing is that before any assignment is made to previous or current, we first evaluate the right hand side and then make the assignment. In here first thing on the right is current, and then we add previous and current and then make previous the current and finally make current the new added value. Another key thing is emphasized in the highlighted part where we decrement i to make the while loop stop when it executes 10 times. Andrew gives his result to Rohin and renders him speechless.

The for statement

As in many other programming languages, the for statement is used to iterate over a piece of code multiple times. However, unlike many other languages (such as Java and C), in Python, the for statement creates a loop over elements of the provided sequence and iterates over a piece of code inside the statement.

Generally we use a while statement to execute a piece of code n times. The for loop is generally used to iterate over a sequence and apply our code on each item until we reach the end of the sequence. The syntax is:

for <name> in <expression>:
    <suite>

To execute a for statement:

  1. Evaluate the <expression> which must yield an iterable (a fancy way of saying that it must return a valid sequence of items)
  2. For each element in that iterable (in order):
    1. Bind <name> to that value in the local environment.
    2. Execute the <suite>.

The above for statement is equivalent to:

iterator = iter(<expression>)
while True:
    try:
        <name> = next(iterator)
    except StopIteration:
        break
    <suite>

Example: Iterating over a string

Lets assume that Andrew wants to get back at Rohin so he dares him to pronounce the longest english word, Pneumonoultramicroscopicsilicovolcanoconiosis, without using a vowel. Rohin thinks that if he had a list of all the characters of the word he can go over each one and write out only the consonants thus making it easier when he is pronouncing. He immediately comes up with a solution that involves a for loop. He provides the fallowing code:

vowels = ["a", "e", "i", "o", "u"]
word = "pneumonoultramicroscopicsilicovolcanoconiosis"
for character in list(word):
    if character not in vowels:	
        print (character, end=" ")     # optional 2nd argument is to print every character in one line

As you can see Rohin creates a list of all the characters of the word by list(word), goes over each character one by one and prints out only the ones that are not vowels. To make things more interesting when we are using while or for statements to iterate, we can make nested loops by putting multiple for statements or while statements inside each other. This nested loop structure helps us iterate over a list of items inside another list of items.

See also

Sources