Objectives:
Upon completion of this lesson, the student will be able to:
Many of you had fun with recursive implementation of factorial. Theoretically we can implement iteration through sequences using similar recursive tricks but it is inefficient.
Thus I would like you to welcome the "workhorse" of programming -- the loop. If recursion is a very powerful construct and used more heavily in functional languages, lambda calculus, and theory of computability in real-life-programming we will simply use loops to either explore sequences of values and iteratively re-execute the same statements until completion or explicit interruption (by user or the system).
for loop is probably the most popular loop construct in Python:
for target in sequence:
do_statements
But so far we have learnt only a single sequence
type:
string = "Yarik knows this stuff well, so will I"
for c in string:
print c,
Note: in above snippet I have used a python 2.x trick to avoid printing new line by adding "," at the line of the print statement
More often you will create/see for loops which operate on lists, tuples and dicts which we will learn next. Meanwhile I will present you with a range
function returning a list from start to (not including) end integer:
# Get input
start = int(raw_input("start? "))
end = int(raw_input("end? "))
# Calculate cumulative sum
csum = 0
for x in range(start, end):
csum += x
print x, csum
print("Exited with x==%d" % x)
More classical, but less frequently used in Python while loop repeats statements while condition
remains True:
while condition do:
do_statements
```
x = start
csum = 0
while x < end:
csum += x
print x, csum
x += 1
print("Exited with x==%d" % x)
Miniquiz
Why do you think for loop had x==9 while while x==10?
Find (at least) 4 bugs in the script below without running it!
#!/usr/bin/ env python
def compute(n):
i = 0; s = 0
while i <= n:
s += random.random()
i += 1
return s/n
n = '10'
print('the average of %d random numbers is %g' % (n, compute(n)))
Excercise
Fix the bugs and refactor to use for loop and range function.
x = start
csum = 0
while True:
csum += x
x += 1
print x, csum
if x >= end:
break
print("Exited with x==%d" % x)
x = start
csum = 0
while x < end:
csum += x
x += 1
if x % 2:
continue # skip printing odd numbers
print x, csum
print("Exited with x==%d" % x)
Excercise
Write a function to compute factorial without recursion. Which loop
ing strategy (for, while, while True + break) will you prefer to use?
Write it as a function (i.e. def factorial(n)
) and reuse your tests from the HW1 to verify its correct operation.
Use %timeit ipython "magic" function to time your recursive and non-recursive implementation -- which will be faster?
Implement using an alternative looping approach (i.e. if you used for, use while and vise versa), %timeit as well. Which one is the winner?
# Example for howto use %timeit
%timeit sqrt(10000)
More excercises
Switch to external editor, e.g. PyCharm, and in a file secret_language.py
Define a function reverse_word, which given a string, returns a string with letters of the original string in inverted order.
Define a function encode_sentence, which given a sentence, swaps each odd word with preceeding its even word.
For each of those functions, provide basic unittests in test_reverse_word and test_reverse_each_word functions. Execute those tests using nosetests to verify correct operation
How will you "decode" a sentence encoded with encode_sentence ?