Notes: Recitation 1
From 6.00 reference wiki
These notes go over the stuff we talked about in recitation. As long as you followed the basic Python review, you should be all set for problem set 0.
Reading these notes is optional. The reading from the book is mandatory.
The notes on functions should clear up some of the stuff we were discussing when we ran out of time.
Contents |
Python Review
Comments, Variables/Types, if-else, Loops
Divide and Conquer
- Break the problem up into smaller, simpler, sub-problems.
- Solve each sub-problem independently.
- Combine these solutions to solve the overall problem.
Breaking up a program into different functions, each of which solves a part of the overall problem, is an example of this approach. For anything other than very simple programs and computer systems, this is the right way to go about implementing solutions.
An introduction to functions
Simply put, a function is a block of code that performs some specific task. For example, the factorial function calculates the factorial of its input.
Functions can have inputs (called arguments or parameters) and may produce an output (called a return value). The return value of a function is unrelated to what it may display (using print statements).
As you will learn throughout this course, functions are an incredibly useful abstraction. They allow code to be reasoned about modularly, and shared easily among different programmers. Programs, especially large ones, are easier to understand when we divide them up into functions, each function having a well-defined description and purpose.
Defining a function
In Python, functions are created with the def keyword:
def hello():
""" greets a person """
print 'Hello'
The name of the function immediately follows the def, and an optional (possibly multi-line) triple-quoted string description of what the function does (meant for human readers) can follow the def line.
The code inside this def is not executed immediately. A variable assignment binds a name to a value, and a def binds a name to a block of code. The code can be executed later, when the function is called.
Calling a function
(the simple case, no inputs, no outputs)
The syntax for calling a function is the name of the function followed by parentheses:
>> hello() Hello
The diagram below shows the code (in the box) being executed:
hello() ------> +---------------+
| print 'Hello' |
... <------ +---------------+
In this case, when Python encounters hello(), it realizes that you are asking it to call the function named hello. The earlier def for hello told Python that the code for the function consists of a single print statement. Therefore, the interepreter will go and execute that print statement. After this, the interpreter will resume the code that follows the hello().
Parameters
A function can also have inputs, or parameters (also called arguments).
def hello(name):
""" greets a person.
parameter: <name> is the person's name.
"""
print 'Hello', name
We can call a function with different parameter values to modify its behaviour:
>> hello('Asfandyar')
Hello Asfandyar
>> hello('John')
Hello John
The diagram below shows a (simplified) illustration of what happens:
hello('Asfandyar') ---> +---------------------+
| name = 'Asfandyar' |
| print 'Hello', name |
<--- +---------------------+
hello('John') --------> +---------------------+
| name = 'John' |
| print 'Hello', name |
<-------- +---------------------+
There can be multiple parameters:
>> def sum(i, j, k):
""" prints the sum of its inputs """
print i + j + k
>> sum(1,2,3)
6
With multiple parameters, variables are matched to input values left-to-right:
sum(1,2,3) ----> +-----------------+
| i = 1 |
| j = 2 |
| k = 3 |
| print i + j + k |
<---- +-----------------+
Return values
So far, all we can do is make our functions print something. Functions can be much more useful than this.
We have the sum function from above. Suppose we want to add two sums together:
y = sum(1,2,3) + sum(4,5,6)
But what happens when we execute the above statement in IDLE?
>> y = sum(1,2,3) + sum(4,5,6) 6 15
And then we see an error.
The Python interpreter calls sum(1,2,3), which prints out 6. Then the interpreter calls sum(4,5,6), which prints out 15. This is what we'd expect.
But then the interpreter reaches the addition step and fails. Neither of the sum calls returned anything, so there is nothing to add. Even though we displayed the values 6 and 15, we did not store them anywhere. Both these values were lost when the code for each sum ended.
To fix this, we need to use a return statement in the function. A return statement is a special way to temporarily store a value, giving it to the function's caller after the function has finished.
>> def sum(i, j, k):
""" returns the sum of its inputs """
n = i + j + k
print n
return n
Now, if we try adding sums we get the expected result:
>> y = sum(1,2,3) + sum(4,5,6) 6 15 >> print y 21
The diagram below shows how the value of y is being calculated:
+----->-------------> +---------------+
| | i = 1 |
| | j = 2 |
| | k = 3 |
| | n = i + j + k |
| (6) | print n |
| +---<--------<---- | return n |
| | +---------------+
| (6)
| |
y = sum(1,2,3) + sum(4,5,6)
| |
(15) +----> +---------------+
| | i = 4 |
| | j = 5 |
| | k = 6 |
| | n = i + j + k |
| | print n |
+------<--- | return n |
(15) +---------------+
Let's walk through a simplified version of how Python interprets this expression, one step at a time.
1. We start with:
y = sum(1,2,3) + sum(4,5,6)
2. The Python interpreter calls sum(1,2,3) and this function returns the value 6 (this is the value of the variable n when the return is reached). Therefore 6 is substituted, after the function has finished:
y = 6 + sum(4,5,6)
3. Now the interpreter calls sum(4,5,6) which returns the value 15, so 15 is substituted as before:
y = 6 + 15
4. Now the interpreter adds the two numbers, leaving:
y = 21
Note: If we removed the print statement from sum, the value of y would be unchanged. If we remove the return statement, we get an error as before. It is important to distinguish what is displayed (using print) from what a function returns (using return). One does not directly affect the other.
Recursion
While programming, we can define a function in terms of itself. This is called recursion.
As an example, suppose we want to implement the function calculate_area which takes a polygon as an input, and returns the area of that polygon.
How would calculate_area do this?
One approach is this:
- If the polygon is a triangle, we know how to calculate the area, so return it.
- Otherwise, divide the polygon into smaller polygons.
- Call calculate_area for each of the smaller polygons.
- Return the sum of all areas.
The technique of recursion is another example of divide-and-conquer. Recursion is a very powerful approach to solving computational problems.
Recursive function: The above is a recursive function: calculate_area calls itself.
Base case: The triangle is the base case. In general, there can be more than one base case. Simply put: it is the case in which the function doesn't need to call itself again, the point where the recursion terminates.
Why isn't this like an infinite loop? Is there some polygon for which calculate_area will never stop?
You can draw this out on paper, or use a simple mathematical proof, to convince yourself that we will always eventually reach the triangle case, so the function will eventually terminate and return an answer.
Stack overflow: Unfortunately, like while loops, we can define recursive functions that would (theoretically) go on forever. The good news is that, unlike while loops, such badly defined recursive functions will eventually lead to a Python stack overflow error, causing the program to stop.
(We will discuss recursion in more detail next week.)
![[Main Page]](../../../../var/www/mediawiki-1.6.3/images/eecs-logo2.png){kind=logo}