Chapter 7: Iteration – Think Python

Hi there!

So, we have made it to Chapter 7.

In case you have not noticed, I have not worked on the exercises from chapter 5 to chapter 7 yet. My goal is to speed up with the theory and then practice for a week. I will organize a session of “Code til you drop” with exercises from Chapter 5 to 8. I hope you can join. This will help us consolidate our knowledge before we tackle Chapter 9’s case study.

The title of chapter 7 is Iteration.

Here is a quick definition in order for us to start:

Iteration is the act of repeating a process with the aim of approaching a desired goal, target or result. Each repetition of the process is also called an “iteration”, and the results of one iteration are used as the starting point for the next iteration.

Source: Wikipedia/Iteration

7.1 Multiple assignment

Let us recall the notion of assignment from Chapter 3 – Functions (Part II):

>>> x = 3 # Read, variable x gets the value of 3.

>>> x = x + 1 # Read, variable x gets the value of itself plus 1.

In addition, we were introduced to Boolean expressions on Chapter 5 / Section 5.1.

>>> 5 == 5 # Read, verify if 5 equals 5.

[…] With multiple assignment it is especially important to distinguish between an assignment operation [ “=” ] and a statement of equality [ “==” ].

Here is the definition that Professor Downey provides for multiple assignment.

Multiple assignment : Making more than one assignment to the same variable during the execution of a program [or code block]

7.2 Updating variables

Do you remember when we first saw this assignment statement “x = x + 1″ in Chapter 3? Today we learn that it is called an assignment update, since the new value of the variable x depends on the old value of x.

>>> x = x + 1 # Read, “get the current value of x, add one (1), and then update x with the new value”.

In order to update a variable, you must initialize the variable first. Otherwise, Python will not recognize the variable.

Python evaluates the right side before it assigns a value to x.

>>> x = 0 # Read, variable x gets the value of zero (0). This assignments is also considered as the initialization of variable x.

>>> x = x + 1  #”Updating a variable by adding one (1) is called an increment“.

>>> x = x 1 1  #”Updating a variable by subtracting one (1) is called an decrement“.

7.3 The while statement

Iteration : Repeated execution of a set of statements using either a recursive function call or a loop.

Python statements that make recursion easier are:

• for statement : ” for i in range ( n ): “
• while statement : ” while Boolean expression : “

Recursion versus For Loop versus While Loop

NOTE: I was looking for a way to improve the “countdown” function with a for loop, and I found inspiration in PythonicProse and Docs/Python.

Here is the flow of execution for the while loop:

1. Evaluate the condition, yielding True or False.
2. If the condition is false, exit the while statement and continue execution at the next statement.
3. If the condition is true, execute the body and loop back to step 1.

The loop’s body should aim to prove the condition false, so that the loop terminates. The body may do so by changing the value of one or more variables.

The objective is to avoid infinite loops.

Infinite loop : A loop in which terminating condition is never satisfied.

>>> def sequence (n):
…     while n != 1:
…             print n,
…             if n%2 == 0:    # n is even
…                     n = n/2
…             else:           #n is odd
…                     n = n * 3 + 1
…
>>> sequence (16)
16, 8, 4, 2
>>> sequence (3)
3, 10, 5, 16, 8, 4, 2
>>>

7.4 Break

The break statement can be used to exit a loop. To illustrate this notion, Professor Downey provides this example:

>>> while True:
…     line = raw_input (‘> ‘)
…     if line == ‘done’:
…             break            # The condition (if line == ‘done’) allows us to stop the condition affirmatively (“stop when this happens”).
…     print line
…
> Hi there!
Hi there!
> done
>>>

The loop condition is True, which is always true, so the loop runs until it hits the break statement.

Each time through, it prompts the user with an angle bracket. If the user types done, the break statement exits the loop.

Exercise 7.1

Re-write the function print_n from Section 5.8 using iteration instead of recursion.

Exercise 7.1) Print_n using a while statement

I tried a couple of times to re-write the print_n function using a while statement. This helped me get it right :

• First, it is useful to remind ourselves that the while statement will execute as long as the conditional is True.
  • So, we can include in the while-block whatever we want to do or display while the function is True.
  • In the print_n function from exercise 7.1, we want to print the variable s as long that the conditional ” n > 0 ” is True.
• Second, a great quality of the while statement is that whenever the conditional is False it ends. Isn’t this great?

7.5 Square roots

Not long ago, I began reviewing some mathematical concepts in order to better tutor mathematics.

So, as we progress in learning the theory and logic behind Python, it amazes me to realize the closeness of mathematics and programming.

For instance, if we were to write a program that computes numerical results, we could use loops in order to start with approximate answers and iteratively improving it.

The book (Think Python) demonstrates this by working with the Newton’s method for computing a square root.

y = ( x + a/x )/2

Netwon’s Method

Professor Downey points out that we must be cautious to test float equality since “floating-point values are only approximately right”.

For instance, irrational numbers such as ∏ (pi) and √2, cannot be represented exactly with a float.

Speaking of ∏ (pi), the book Moonwalking with Einstein: the Art and Science of Remembering Everything mentions that there are people that have memorized hundreds of digits from pi. This give us a sense of how the float 3.1416 is a rough approximation.

Rather than checking whether x and y are exactly equal, it is safer to use the built-in function abs to compute the absolute value, or magnitude, of the difference between them:

if abs (y – x) < epsilon:

    break

Where epsilon has a value like 0.0000001 that determines how close is close enough.

Exercise 7.2) Encapsulate this loop in a function called square_root that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a.

In interactive mode (using Python in the Terminal), I wrote:

>>> a = 4.0
>>> x = 3.0
>>> while True:
…     print x
…     y = (x + a/x)/2
…     if abs (y-x) < epsilon:
…             break
…     x = y
>>>

NOTE: I had the following error when I wrote the code block:

Traceback (most recent call last):
File “<stdin>”, line 4, in <module>
NameError: name ‘epsilon’ is not defined
>>>

So, I tried to write it in script mode (using Sublime Text and then executing it with the Terminal) and importing the math module.

Also, I looked for more information and I found an interesting/useful links:

• The Floating-Point Guide
• Two Simple Equations to Compute PI

Here is the code block in script mode (using Sublime Text):

from math import *
EPSILON = 0.0000001
a = 4.0
x = 3.0
while True:
print x
y = (x + a/x)/2
if abs (y-x) < EPSILON:
break
x = y

To verify the answer, I executed the file (sqroot_epsilon.py) via the Terminal. Here is the outcome!

MacBook-Air-xxxx:Desktop xxxx$ python sqroot_epsilon.py
3.0
2.16666666667
2.00641025641
2.00001024003
2.00000000003
MacBook-Air-xxxx:Desktop xxxx$

Later, I realized that the variable named epsilon had to be set before hand. So, the code block can perfectly work in script or interactive mode.

7.6 Algorithms

So, here we are on the verge of understanding the algorithm notion. I asked countless times what was an algorithm. The best answer I got was that it was like a recipe. Fair enough. However, I could not understand why a simple recipe was so fascinating in the programming world.

Again, Professor Downey has done a tremendous work explaining the coveted notion. He starts his explanation by explaining what an algorithm is not. He provides the memorization of the multiplication tables as an example.

However, he points out an interesting fact. As kids, we developed shortcuts or tricks.

For example, to find the product of n and 9, you can write n – 1 as the first digit and 10 – n as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm!

We can link this explanation with the recipe one. However, the later is crystal clear.

7.7 Debugging

The bigger the program is, the greater the possibility of making errors. Thus, we can say that a program’s length and the possibility of making an error are positively correlated.

Nevertheless, we can save time and many hair pulled by “debugging by bisection”. We can roughly cut the program in two and  test one part and then the other. We can use the incremental development technique we learned in Chapter 6 and use the print statements to verify line by line (or small code blocks) if we want.

***

Acknowledgments :

These notes represent my understanding from the book Think Python: How to Think Like a Computer Scientist written by Allen B. Downey.

Part of the chapter is transcribed and all the quotes unless specified otherwise come directly from his book.

Thank you Professor Downey for making this knowledge available.

 

Also, I would like to thank the open source community for their valuable contribution in making resources on programming available.

Thank you