Difference between revisions of "Iteration"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(copyedit lead)
m (For loop: Added link to Rohin's guide)
 
(20 intermediate revisions by one user not shown)
Line 2: Line 2:
 
'''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.
 
'''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 <code>while</code> statement==
+
==Types of loops==
The simplest form of iteration is the <code>while</code> [[statement]]. A <code>while</code> statement contains an expression header and a suite of expressions:
+
The ''while loop'' is generally used to execute a piece of code an indefinite number of times until a condition is met.
 +
 
 +
The ''for loop'' is generally used to repeat a piece of code <code>n</code> times (for each item of a sequence).
 +
 
 +
===While loop===
 +
A <code>while</code> loop consists of a condition and a suite of statements:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
while <expression>:
+
while condition:
     <suite>
+
     # suite
 
</syntaxhighlight>
 
</syntaxhighlight>
  
To execute a <code>while</code> statement:
+
A <code>while</code> loop executes its suite as long as <code>condition</code> evaluates to a <code>True</code> value. <code>condition</code> is checked each time before executing the suite again. If <code>condition</code> evaluates to a <code>False</code> value, execution continues with the statements after the while loop.
# execute the header expression.
+
# if it is <code>True</code>, execute the suite of expressions and return to step 1.
+
  
This where you should be careful. The entire suite of expressions is evaluated before we return and check the header expression again. A while statement executes its suite until the header expression evaluates to a <code>False</code> value. Then it stops and computer continues executing the remaining parts of the program after the while statement block. If a while statement doesn't stop it is called an '''infinite loop'''. In the Python interpreter press <Control>-C to terminate the execution.
+
If the suite does not modify the variables being tested in <code>condition</code>, the loop will run forever. This is called an ''infinite loop''. In the Python interpreter, press <Control>-C to terminate the program.
  
===Example: First 10 fibonacci numbers===
+
==== Simple example ====
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. Now fibonacci sequence is a special mathematical sequence where every other number is created by adding previous two numbers. Andrew knows that fibonacci sequence starts with 1 1 2 however lets assume that he doesn't know the rest. So he creates this logic. 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 his '''while''' statement. He writes:
+
The following while loop prints the numbers 0 &ndash; 5:
<syntaxhighlight lang="python" highlight=6>
+
<syntaxhighlight lang="python">
 +
>>> i = 0
 +
>>> while i <= 5:
 +
...    print(i)
 +
...    i += 1
 +
...
 +
0
 +
1
 +
2
 +
3
 +
4
 +
5
 +
</syntaxhighlight>
 +
 
 +
====Example: First 10 Fibonacci numbers====
 +
One day Rohin challenges 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 following numbers are obtained by adding previous two numbers. Andrew can start with the first two values of the sequence, add those two numbers to create the 3rd number, add the 2nd and 3rd numbers to create the 4th, add the 3rd and 4th to create the 5th, and so on. He realizes that the problem can be solved iteratively, so he uses a while loop:
 +
<syntaxhighlight lang="python" line>
 
i = 10
 
i = 10
 
previous = 0
 
previous = 0
Line 27: Line 46:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Remember in the assignment <code>previous, current = current, previous + current</code> the key thing is that '''before''' any assignment is made to previous or current first we evaluate the right part 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''' the value of i to make the while loop stop when it executes 10 times. Andrew gives his result to Rohin and renders him speechless.
+
Recall that in the assignment <code>previous, current = current, previous + current</code> (line 5), the right side of the equals sign is evaluated first before making any assignment to <code>previous</code> or <code>current</code>. In this case, we evaluate <code>current</code>, and add <code>previous</code> and <code>current</code>, and then set <code>previous</code> to the value we got from evaluating <code>current</code> and set <code>current</code> to the result of the addition.
  
==The <code>'''for'''</code> statement==
+
<code>i = i - 1</code> (line 6) ''decrements'' <code>i</code> to make the while loop stop when <code>i</code> is 0 (i.e., make it execute 10 times).
Like in many other programming languages <code>for</code> statement is used when we want to iterate over a piece of code multiple times hence it is another way to create iteration. However ''unlike'' many other languages (such as C) Python <code>for</code> statement creates loop over '''items''' of a specific sequence that we provide and iterates over a piece of code inside the for statement block. Generally we use a while statement if we want to iterate a piece of code ''n'' times however with the for loop we can iterate over a sequence of items and apply our code on each item '''until''' we reach the end of the sequence. The syntax is:
+
 
 +
===For loop===
 +
In languages such as Java and C, the for loop iterates over a range of values. By contrast, Python's for loop loops over ''elements of a sequence''. The syntax is:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
for <name> in <expression>:
+
for elem in iterable:
     <suite>
+
     # suite
 
</syntaxhighlight>
 
</syntaxhighlight>
 
To execute a <code>for</code> statement we fallow these steps:
 
#Evaluate the <expression> which must yield an [[iterable]] value (a fancy way of saying that it must return a valid sequence of items)
 
# For '''each''' element value in that sequence '''in order''':
 
## Bind <name> to that value in the ''local'' environment.
 
## Execute the <suite>.
 
  
Do these steps for every value in the sequence until the end of the sequence. When we reach the end the for statement executes for the last item and stops. In retrospect for statement might be "safer" way to deal with iteration since we might not have to deal with a boolean creating an infinite loop as it is the case with the while statement. Yet while statement is still a more direct way to create iteration if we simply one to execute a piece of code ''n'' times.
+
To execute a for loop:
 +
# Evaluate <code>iterable</code>, which must yield an [[iterable]] (a fancy way of saying that it must return a valid sequence of items)
 +
# For each element in that iterable (in order):
 +
## Bind <code>elem</code> (you can call it whatever you want) to that value in the local environment.
 +
## Execute the suite.
  
===Example: Iterating over a [[string]]===
+
The above for loop is equivalent to:
Lets assume that Andrew wants to get back at Rohin so he dares him to pronounce the longest english word,  [http://en.wikipedia.org/wiki/Pneumonoultramicroscopicsilicovolcanoconiosis 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:
+
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
vowels = ["a", "e", "i", "o", "u"]
+
iterator = iter(iterable)
 +
while True:
 +
    try:
 +
        elem = next(iterator)
 +
    except StopIteration:
 +
        break
 +
    # suite
 +
</syntaxhighlight>
 +
 
 +
====Simple example====
 +
The following code prints each element of the list (recall that a list is an iterable):
 +
<syntaxhighlight lang="python">
 +
>>> lst = [1, 2, 3]
 +
>>> for elem in lst:
 +
...    print(elem)
 +
...
 +
1
 +
2
 +
3
 +
</syntaxhighlight>
 +
 
 +
====Example: Iterating over a [[string]]====
 +
Andrew dares Rohin to pronounce the longest English word, {{Plain link|//en.wikipedia.org/wiki/Pneumonoultramicroscopicsilicovolcanoconiosis|Pneumonoultramicroscopicsilicovolcanoconiosis}}, without vowels. Rohin realizes that he can loop over all the characters of the word and print out only the ones that are not vowels, making it easier to pronounce:
 +
<syntaxhighlight lang="python">
 +
vowels = "aeiou"
 
word = "pneumonoultramicroscopicsilicovolcanoconiosis"
 
word = "pneumonoultramicroscopicsilicovolcanoconiosis"
for character in list(word):
+
for character in word:
 
     if character not in vowels:
 
     if character not in vowels:
         print (character, end=" ")     # optional 2nd argument is to print every character in one line
+
         print(character, end="") # optional 2nd argument is to print everything on one line
 +
</syntaxhighlight>
 +
 
 +
====Using user-defined [[Iterator|iterators]]====
 +
{{Main|For Loops and Iterators}}
 +
 
 +
==Nested loops==
 +
A ''nested loop'' is a loop inside a loop. The first pass of the outer loop triggers the inner loop, which executes to completion. Then the second pass of the outer loop triggers the inner loop again. This repeats until the outer loop finishes.
 +
 
 +
Nested loops are useful in traversing an iterable object within an iterable object. Example:
 +
<syntaxhighlight lang="python">
 +
# print all integer coordinates (x, y), where 0 <= x, y <= 5
 +
for i in range(6):
 +
    for j in range(6):
 +
        print("({0}, {1})".format(i, j))
 +
</syntaxhighlight>
 +
 
 +
==<code>break</code> statement==
 +
The <code>break</code> statement exits out of a loop. Example:
 +
<syntaxhighlight lang="python">
 +
>>> for x in range(6):
 +
...    if x == 3:
 +
...        break
 +
...    print(x)
 +
...
 +
0
 +
1
 +
2
 +
</syntaxhighlight>
 +
 
 +
==<code>continue</code> statement==
 +
The <code>continue</code> statement skips the rest of the code in the suite and goes to the next iteration. Example:
 +
<syntaxhighlight lang="python">
 +
>>> for x in range(6):
 +
...    if x == 3:
 +
...        continue
 +
...    print(x)
 +
...
 +
0
 +
1
 +
2
 +
4
 +
5
 
</syntaxhighlight>
 
</syntaxhighlight>
  
As you can see Rohin creates a list of all the characters of the word by <code>list(word)</code>, 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 ==
 +
* [[Iteration vs. recursion]]
  
 
== Sources ==
 
== Sources ==

Latest revision as of 13:48, 27 July 2014

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.

Types of loops

The while loop is generally used to execute a piece of code an indefinite number of times until a condition is met.

The for loop is generally used to repeat a piece of code n times (for each item of a sequence).

While loop

A while loop consists of a condition and a suite of statements:

while condition:
    # suite

A while loop 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 condition, 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 – 5:

>>> i = 0
>>> while i <= 5:
...     print(i)
...     i += 1
... 
0
1
2
3
4
5

Example: First 10 Fibonacci numbers

One day Rohin challenges 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 following numbers are obtained by adding previous two numbers. Andrew can start with the first two values of the sequence, add those two numbers to create the 3rd number, add the 2nd and 3rd numbers to create the 4th, add the 3rd and 4th to create the 5th, and so on. He realizes that the problem can be solved iteratively, so he uses a while loop:

  1. i = 10
  2. previous = 0
  3. current = 1
  4. while i > 0:
  5.     previous, current = current, previous + current
  6.     i = i - 1
  7.     print(previous)

Recall that in the assignment previous, current = current, previous + current (line 5), the right side of the equals sign is evaluated first before making any assignment to previous or current. In this case, we evaluate current, and add previous and current, and then set previous to the value we got from evaluating current and set current to the result of the addition.

i = i - 1 (line 6) decrements i to make the while loop stop when i is 0 (i.e., make it execute 10 times).

For loop

In languages such as Java and C, the for loop iterates over a range of values. By contrast, Python's for loop loops over elements of a sequence. The syntax is:

for elem in iterable:
    # suite

To execute a for loop:

  1. Evaluate iterable, 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 elem (you can call it whatever you want) to that value in the local environment.
    2. Execute the suite.

The above for loop is equivalent to:

iterator = iter(iterable)
while True:
    try:
        elem = next(iterator)
    except StopIteration:
        break
    # suite

Simple example

The following code prints each element of the list (recall that a list is an iterable):

>>> lst = [1, 2, 3]
>>> for elem in lst:
...     print(elem)
... 
1
2
3

Example: Iterating over a string

Andrew dares Rohin to pronounce the longest English word, Pneumonoultramicroscopicsilicovolcanoconiosis, without vowels. Rohin realizes that he can loop over all the characters of the word and print out only the ones that are not vowels, making it easier to pronounce:

vowels = "aeiou"
word = "pneumonoultramicroscopicsilicovolcanoconiosis"
for character in word:
    if character not in vowels:	
        print(character, end="") # optional 2nd argument is to print everything on one line

Using user-defined iterators

Main article: For Loops and Iterators

Nested loops

A nested loop is a loop inside a loop. The first pass of the outer loop triggers the inner loop, which executes to completion. Then the second pass of the outer loop triggers the inner loop again. This repeats until the outer loop finishes.

Nested loops are useful in traversing an iterable object within an iterable object. Example:

# print all integer coordinates (x, y), where 0 <= x, y <= 5
for i in range(6):
    for j in range(6):
        print("({0}, {1})".format(i, j))

break statement

The break statement exits out of a loop. Example:

>>> for x in range(6):
...     if x == 3:
...         break
...     print(x)
... 
0
1
2

continue statement

The continue statement skips the rest of the code in the suite and goes to the next iteration. Example:

>>> for x in range(6):
...     if x == 3:
...         continue
...     print(x)
... 
0
1
2
4
5

See also

Sources