Week 5: Notes

conditional expressions

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 j

We can rewrite it using a conditional expression:

def greater(i, j):
    return i if abs(i) >= abs(j) else j

A conditional expression always has the form

expression if condition else expression

The keyword else must always be present (unlike in an ordinary if statement).

(If you already know C or another C-like language, you may notice this feature's resemblance to the ternary operator (? :) in those languages.)

None

None is a special value in Python that represents nothingness. It is often useful to represent the absence of a value.

For example, here's a program that computes the maximum of all numbers read from standard input. It keeps the maximum in a variable 'mx', which is initialized to None before any numbers are read:

import sys

mx = None

for line in sys.stdin:
    x = int(line)
    if mx == None or x > mx:
        mx = x

print(f'max = {mx}')

Be aware that the Python REPL prints nothing at all when you give it an expression whose value is None:

>>> x = None
>>> x
>>>

If a function does not return a value explicitly, then it will return None. Also, if a return statement does not contain a value, it will return None. For example, consider this function:

def prime_check(n):
    for i in range(2, n):
        if n % i == 0:
            print('composite')
            return
        
    print('prime')

Let's call it:

>>> prime_check(14)
composite
>>> prime_check(23)
prime

In both cases the function returned None, and so the REPL didn't print any return value for the function.

(None is similar to the special value null in some other languages such as Java and C#.)

local and global variables, continued

In the last lecture we introduced the concept of local variables and global variables. Now consider this program, with two global variables at the top:

a = 10
b = 20

def abc(n):
    a = n
    return a + b

Let's try it:

>>> abc(50)
70
>>> a
10
>>>

We can see that the assignment "a = n" above did not set the value of the global a. Instead, it set a local variable called a. However, the statement "return a + b" did read the value of the global variable b.

What if we want the function abc() to set the global a? To achieve that, we can add a global declaration to the function:

def abc(n):
    global a
    a = n
    return a + b

Now calling abc() will set a:

>>> abc(100)
120
>>> a
100

We see that a function can read the value of a global variable without declaring it as global. But if a function wants to assign to a global variable, it must declare the variable as global.

To be more precise, here is how Python determines whether each variable in a function is local or global:

When you write a larger program, it's best to have few global variables whose values may change, or even none. They can make a program hard to understand, since any code in the entire program could possibly modify them.

On the other hand, globals that you only read from are fine - essentially they just represent constant data. In Python, by convention we usually capitalize the names of such globals to emphasize that they are constant. For example:

SECONDS_PER_DAY = 24 * 3600

passing by value and reference

Consider this function, which adds all values in a list (or other iterable):

def sum_of(a):
    s = 0
    for x in a:
        s += x
    return s

Let's call it with a list of 1,000,000 elements:

>>> l = 1_000_000 * [5]
>>> sum_of(l)
5000000

When we called the function, did it copy the list when it passed it to the function? Actually no. The function only received a pointer to the list. To see this more easily, let's write a function that modifies a list element:

def inc(a):
    a[0] += 1

And let's call it:

>>> l = [2, 4, 6]
>>> inc(l)
>>> l
[3, 4, 6]

We see that Python passes lists by reference. When the program calls inc(l), then as the function runs l and a are the same list. If we modify the list in the function, the change is visible in the caller.

The opposite of passing by reference is passing by value, in which the function receives a copy of the data that is passed. In some languages (e.g. C++), an array may be passed by value.

For a large data structure such as an array with 1,000,000 elements, passing by reference will be much more efficient than passing by value. And in fact Python passes references when you pass any value to a function (except for a few small values such as None, True and False, though you can't easily tell the difference since these are immutable).

Now, strictly speaking, Python actually passes references to objects by value. This means that when you pass an object to a function, the function parameter receives a reference to the object, however it is a separate reference than the one in the caller. For example:

def foo(x):
    x = 'hello'

>>> y = 'yo'
>>> foo(y)
>>> y
'yo'

def bar(a):
    a[0] = 100
    a = [2, 4, 6]

>>> b = [0, 0, 0]
>>> bar(b)
>>> b
[100, 0, 0]

When we call the function foo(), x refers to the same string as y (the string is not copied). However, assigning to x does not change y, because x is a separate reference.

Similarly, when we call the function bar(), a refers to the same array as b (the array is not copied). If we modify that array, the change is visible in b. However, assigning to a does not change b, because a is a separate reference.

Many other languages such as Java, C#, and JavaScript use the same calling mechanism.

variable numbers of arguments

We may sometimes wish to write a function that can take a variable number of arguments. For example, we may wish to write a function that returns the average of all its arguments, no matter how many there are:

>>> avg(1.0, 3.0, 8.0)
4.0
>>> avg(2.0, 4.0, 6.0, 8.0, 10.0)
6.0

We may write this function using a parameter preceded by the character '*', which means that the parameter should gather all of its arguments into a tuple:

def avg(*args):
    return sum(args) / len(args)

When we make the call 'avg(1.0, 3.0, 8.0)', inside the function the variable 'args' has the value (1.0, 3.0, 8.0), which is a tuple of 3 values. (Recall that the sum() and len() functions work on tuples just as they do on lists and other sequences).

A parameter preceded by '*' can have any name, but the name 'args' is conventional in Python.

When we call a function we may sometimes have a list (or other sequence) that contains the arguments we'd like to pass. In this case, we can specify '*' before an argument to specify that Python should explode its values into separate arguments. For example, consider this function:

def add(x, y, z, q):
    return x + y + z + q + 10

When we call it, we may specify its arguments individually, or by exploding them from a list:

>>> add(10, 20, 30, 40)
110
>>> l = [10, 20, 30, 40]
>>> add(*l)
110

More commonly, this situation occurs when a function accepts a variable number of arguments, and we want to pass arguments from a list. For example, calling the avg() function we defined above:

>>> l = [3.0, 4.0]
>>> avg(*l)
3.5

recursion

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, suppose we we'd like to write a function that computes n! for any positive integer n. Recall that

n! = n · (n – 1) · … · 3 · 2 · 1

We may write this function iteratively, i.e. using a loop:

def factorial_iter(n):
    p = 1

    for i in range(1, n + 1):
        p *= i

    return p

Alternatively, we 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, 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.)

How does this function work, exactly? Suppose that we call factorial(3). It will call factorial(2), which calls factorial(1), which calls factorial(0). The call stack in memory now looks like this:

factorial(3)
→ factorial(2)
  → factorial(1)
    → factorial(0)

Now

We see that given any n, the function returns the sum 1 * 2 * 3 * … * n = n!.

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 is some general advice for writing a recursive function. First look for a base case where the function can return immediately. (In some problems there will actually be more than one base case.) 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.

more recursive examples

Here's another example. Consider this implementation of Euclid's algorithm that we saw in Introduction to Algorithms:

# gcd, iteratively
def gcd(a, b):
    while b > 0:
        a, b = b, a % b

    return a

We 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 (in our algorithms class) 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.

file input/output

The open() function opens a file. It takes two parameters: a filename plus an optional mode string, which can contain one or more of these characters:

If you don't specify a mode string, the file will be opened for reading in text mode.

When you open a file in text mode, Python will perform universal newline translation, i.e. translate any sort of newlines to '\n'. We will only use text mode in this course.

open() returns a file object. When reading, the file object is iterable: you can loop over it with for to receive a sequence of lines, just like with sys.stdin. When a file is opened for writing, you may write lines to the file by calling the write() method on the file object once for each output line.

When we are finished reading or writing data, you should call close() to close the file.

Here's a program that opens two files called 'input.txt' and 'output.txt'. It reads lines from the input file and writes them to the output file, duplicating every line as it writes:

input = open('input.txt', 'r')    # open for reading ('r' is default mode)
output = open('output.txt', 'w')     # open for writing

for line in input:
    output.write(line)      # write line to output
    output.write(line)      # write it again

input.close()
output.close()

You can read about more methods for input and output in our Python quick library reference.

The with statement

Whenever you open a file, you'll want to close it, even if your program exits unexpectedly with an error. Python has a special statement that makes this easy. The with statement assigns a file object (or other resource) to a variable, then runs a block of code. When the block of code exits for any reason, the object is automatically closed, just as if you had called close() on the object.

Let's rewrite the previous program using with:

with open('input.txt', 'r') as input:    # open for reading ('r' is default mode)
    with open('output.txt', 'w') as output:     # open for writing
        for line in input:
            output.write(line)      # write line to output
            output.write(line)      # write it again

It's good practice to use 'with' whenever you open a file, to ensure that the file will be closed even if the program exits with an error.

In fact with also works with other types of objects that need to be closed, such as network sockets. We may see some of these later in this course.