Week 6: Notes
Some of today's topics are covered in these sections of Think Python:
5.8 Recursion
19.2 List comprehensions
Here are some additional notes.
In Python, you may use if
and else inside an expression;
this is called a conditional expression.
For example, consider this code:
if x > 100:
print('x is big')
else:
print('x is not so big')We may rewrite it using a conditional expression:
print('x is ' + ('big' if x > 100 else 'not so big'))As another example, here is a function that takes two integers and returns whichever has the greater magnitude (i.e. absolute value):
def greater(i, j):
if abs(i) >= abs(j):
return i
else:
return jWe can rewrite it using a conditional expression:
def greater(i, j):
return i if abs(i) >= abs(j) else j(If you already know C or another C-like language, you may notice this feature's resemblance to the ternary operator (? :) in those languages.)
We've already seen that Python supports multiple assignment. For example:
>>> x, y = 15, 20 >>> x 15 >>> y 20
More generally, the left-hand side of an assignment statement may contain a pattern that looks like a tuple or list that holds variable names. When the statement runs, all the variables are assigned values that match the right-hand side:
>>> x, y = 15, 20 >>> x 15 >>> y 20 >>> (x, y) = (25, 30) >>> x 25 >>> y 30 >>> [x, y, z] = [5, 10, 20] >>> x 5 >>> y 10 >>> z 20 >>> ((x, y), (z, q)) = ((1, 3), (7, 9)) >>> x + y + z + q 20
In fact Python is quite lenient. In an assignment statement of this sort, the right-hand side may be any sequence (e.g. a string or range), and the pattern on the left may use either list or tuple syntax, irrespective of the sequence type:
>>> [x, y] = (10, 20) >>> x 10 >>> y 20 >>> (w, x, y, z) = 'cake' >>> w 'c' >>> x 'a' >>> y 'k' >>> z 'e'
A 'for' loop may contain a pattern that is matched to each element in the iteration. This syntax is convenient and makes programs easy to read. For example, consider this loop:
points = [(4, 5), (3, 10), (2, 8), (6, 1)]
for p in points:
print(f'x = {p[0]}, y = {p[1]}, sum = {p[0] + p[1]}')
We may rewrite it using a pattern "x, y" in the 'for' statement:
points = [(4, 5), (3, 10), (2, 8), (6, 1)]
for (x, y) in points:
print(f'x = {x}, y = {y}, sum = {x + y}')
The second version is easier to read.
Note that in this loop we
may write either 'for
x, y in points' or 'for
(x, y) in points'. The first version is slightly more
compact, but in the second version the pattern looks just like the
data that it is matching, which is arguably clearer.
A list comprehension is an expression that loops over a sequence and collects a series of computed values into a list. List comprehensions are powerful and convenient, and we will use them often.
For example, consider this loop that builds a list of all perfect squares from 1 to 400:
squares = []
for i in range(1, 21):
squares.append(i * i)We may replace the three lines above by a single line with a list comprehension:
squares = [i * i for i in range(1, 21)]
In general, a list comprehension may have the form
[ <expression> for <var> in <sequence> ]
A comprehension of this form will loop over the given <sequence>. On each loop iteration, it sets <var> to the value of an element of the sequence, then evaluates the given <expression>. All results are collected into a list.
Here are some more examples of list comprehensions. This comprehension builds a list of numbers from 1 to 20 and their squares:
>>> [(i, i * i) for i in range(1, 11)] [(1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81), (10, 100)]
We may add 1 to each element in a list:
>>> l = [2, 5, 7, 10]
>>> [i + 1 for i in l]
[3, 6, 8, 11]
Here's a function that builds a nested list representing a matrix of zeroes:
def empty(rows, cols):
return [cols * [0] for r in range(rows)]A list comprehension may have an if clause containing an arbitrary condition. Only list elements that satisfy the condition are included in the generated list.
For example, this comprehension collects all characters in the string 'watermelon' that are in the second half of the alphabet:
>>> [c for c in 'watermelon' if c >= 'n'] ['w', 't', 'r', 'o', 'n']
Here's a 1-line solution to Project Euler's Problem 1 (find the sum of all the multiples of 3 or 5 below 1000):
>>> sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])
233168
A list comprehension may have more than one 'for' clause. The 'for' clauses represent a nested loop. All values generated by the inner loop are collected into the resulting list.
For example, this comprehension generates all pairs of values (x, y), where 0 ≤ x, y < 3:
>>> [(x, y) for x in range(3) for y in range(3)] [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
The following comprehension is similar, but in it 'y' only iterates up to the value 'x', so it only generates pairs where y < x:
>>> [(x, y) for x in range(3) for y in range(x)] [(1, 0), (2, 0), (2, 1)]
The comprehension above is equivalent to the following:
l = []
for x in range(3):
for y in range(x):
l.append( (x, y) )
Notice that when there are multiple 'for' clauses in a single comprehension:
The first 'for' clause represents the outer loop.
The comprehension generates a 1-dimensional list, not a list of lists.
As a larger example, here's a comprehension that finds all triples of integers (a, b, c) such that a2 + b2 = c2, with 0 ≤ a < b < c ≤ 20:
>>> [(a, b, c) for c in range(21)
for b in range(c)
for a in range(b)
if a * a + b * b == c * c]
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]A recursive function calls itself. Recursion is a powerful technique that can help us solve many problems.
When we solve a problem recursively, we express its solution in terms of smaller instances of the same problem. The idea of recursion is fundamental in mathematics as well as in computer science.
As a first example, consider this function that computes n! for any positive integer n. (Recall that n! = n · (n – 1) · … · 3 · 2 · 1.) It uses a loop, so this is an iterative function:
def factorial(n):
p = 1
for i in range(1, n + 1):
p *= i
return pWe can rewrite this function using recursion. Now it calls itself:
def factorial(n):
if n == 0:
return 1 # 0! is 1
return n * factorial(n - 1)Whenever we write a recursive function, there is a base case and a recursive case.
The base case is an instance that we can solve immediately. In the function above, the base case is when n == 0. A recursive function must always have a base case – otherwise it would loop forever since it would always call itself!
In the recursive case, a function calls itself recursively, passing it a smaller instance of the given problem. Then it uses the return value from the recursive call to construct a value that it itself can return.
In the recursive case in this example, we
recursively call factorial(n -
1). We then multiply its return value by
n, and return that value. That works because
n! = n · (n – 1)! whenever n ≥ 1
(In fact, we may treat this equation as a recursive definition of the factorial function, mathematically speaking.)
We have seen that we can write the factorial function either iteratively (i.e. using loops) or recursively. In theory, any function can be written either iteratively or recursively. We will see that for some problems a recursive solution is easy and an iterative solution would be quite difficult. Conversely, some problems are easier to solve iteratively. Python lets us write functions either way.
Here's another example. Consider this implementation of Euclid's algorithm that we saw in Intro to Algorithms:
# gcd, iteratively
def gcd(a, b):
while b > 0:
a, b = b, a % b
return aWe can rewrite this function using recursion:
# gcd, recursively
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
Broadly speaking, we will see that
"easy" recursive functions such as gcd
call themselves only once, and it
would be straightforward to write them either iteratively or
recursively. Soon
we will see recursive
functions that call themselves two or more times. Those functions
will let us solve more difficult tasks that we could not easily solve
iteratively.
Here is another example of a recursive function:
def hi(x):
if x == 0:
print('hi')
return
print('start', x)
hi(x - 1)
print('done', x)If we call hi(3), the output will be
start 3 start 2 start 1 hi done 1 done 2 done 3
Be sure you understand why the lines beginning with 'done' are printed. hi(3) calls hi(2), which calls hi(1), which calls hi(0). At the moment that hi(0) runs, all of these function invocations are active and are present in memory on the call stack:
hi(3)
→ hi(2)
→ hi(1)
→ hi(0)Each function invocation has its own value of the parameter x. (If this procedure had local variables, each invocation would have a separate set of variable values as well.)
When hi(0) returns, it does not exit from this entire set of calls. It returns to its caller, i.e. hi(1). hi(1) now resumes execution and writes 'done 1'. Then it returns to hi(2), which writes 'done 2', and so on.
Here is another recursive function:
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n - 1)What does this function do? Suppose that we call sum(3). It will call sum(2), which calls sum(1), which calls sum(0). The call stack now looks like this:
sum(3)
→ sum(2)
→ sum(1)
→ sum(0)Now
sum(0) returns 0 to its caller sum(1).
sum(1) takes this value 0, adds n = 1 to it and returns 1 to sum(2).
sum(2) takes this value 1, adds n = 2 to it and returns 3 to sum(3).
sum(3) takes this value 3, adds n = 3 to it and returns 6.
We see that given any n, the function returns the sum 1 + 2 + 3 + … + n.
We were given this function and had to figure out what it does. But more often we will go in the other direction: given some problem, we'd like to write a recursive function to solve it. How can we do that?
Here is some general advice. To write any recursive function, first look for base case(s) where the function can return immediately. Now you need to write the recursive case, where the function calls itself. At this point you may wish to pretend that the function "already works". Write the recursive call and believe that it will return a correct solution to a subproblem, i.e. a smaller instance of the problem. Now you must somehow transform that subproblem solution into a solution to the entire problem, and return it. This is really the key step: understanding the recursive structure of the problem, i.e. how a solution can be derived from a subproblem solution.