2010 September 25 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Assignment: Recursion

Carleton College CS 201, Prof. Joshua R. Davis

Introduction

Recursion refers to any situation in which a function invokes itself. Recursion is used heavily in computer science and computer programming. You probably first encountered it in CS 111, but only briefly; we'll use it throughout the rest of this course. Recursion can be tricky at first, but after some practice it becomes quite natural. Hence this assignment — a collection of short exercises about recursion.

You must complete and hand in this assignment individually, not with any partner, although as always you are encouraged to bounce ideas off other students. The assignment is due at the beginning of class on Wednesday.

Write Three List Operations

When you first started using Python lists, you wrote a lot of for loops and while loops. Soon you probably realized that most of them were pretty similar: you perform a certain operation on every item of the list, or you test which items satisfy a certain criterion, or you combine the items using a certain function. These three kinds of tasks are called mapping, filtering, and folding (a.k.a. reducing).

In this section you'll implement these three functions for the List data structure from Assignment: Efficiency. Write your code in a file recursion.py according to the following specifications. Your implementations must be recursive (although they could be done iteratively too).

For example, suppose we define 
def square(x):
	return x * x

def isEven(x):
	return x % 2 == 0

def add(x, y):
	return x + y

def subtract(x, y):
	return x - y
and suppose that the list myList is (1, -7, 4, 12). Then here's what happens: 
>>> print listMap(square, myList)
(1, 49, 16, 144)
>>> print listFilter(isEven, myList)
(4, 12)
>>> print listFold(add, myList)
10
>>> print listFold(subtract, myList)
-8
In case it's still not clear, the first listFold computes ((1 + -7) + 4) + 12, and the second listFold computes ((1 - -7) - 4) - 12. If your second listFold produces 0, then maybe you accidentally computed 1 - (-7 - (4 - 12))?

Once they're part of your vocabulary, the mapping, filtering, and folding operations can expedite a surprising number of programming tasks. The only inconvenient part of the process is writing the helper functions square, isEven, etc. Frankly, it's tedious. This is where Python's anonymous function feature comes in handy. Using the lambda keyword, you can make a little function, that doesn't even have a name, for one-time use. For example, the following code is equivalent to the code above, but doesn't require defining any helper functions. 

>>> print listMap((lambda x: x * x), myList)
(1, 49, 16, 144)
>>> print listFilter((lambda x: x % 2 == 0), myList)
(4, 12)
>>> print listFold((lambda x, y: x + y), myList)
10
>>> print listFold((lambda x, y: x - y), myList)
-8

Here's a more applied example. Suppose that you're writing a program to manage employee records at a large company. Each employee is an object of class Employee; you have all of the employees in a List employees. You want to know the largest salary at the company. Here's what you might do: 

salariedEmployees = listFilter((lambda e: e.isSalaried()), employees)
salaries = listMap((lambda e: e.getSalary()), salariedEmployees)
largestSalary = listFold(max, salaries)

Or suppose that you're a physicist doing a problem involving point particles in one dimension. You have a List particles. You want to compute the moment of inertia of these particles with respect to some given location x. Here it is in one line. 

moment = listFold((lambda x, y: x + y), listMap((lambda p: p.getMass() * (p.getX() - x)**2), particles))

Although they don't describe every task that we might want to do with lists, the mapping, filtering, and folding operations are really handy. They come built-in for Python lists; see map, filter, and reduce. Notice also that the mapping and filtering operations are parallelizable: the items in the list are independent of each other, so that one computer can work on one part of a big list while other computers work on other parts of the list. Recently, Google has released a programming library, MapReduce, that implements this functionality on a massive scale (potentially hundreds of thousands of computers). More recently still, Google has moved away from using the product. Understanding exactly why is interesting but beyond the scope of this course.

Write powerSet

In this section you'll write one recursive function for manipulating the Set data structure from Assignment: Classes. Put your code in the same file recursion.py. Here is the specification.

Here's a transcript of the function in action: 
>>> from set import Set
>>> s = Set()
>>> print powerSet(s)
{{}}
>>> s.add('a')
>>> print powerSet(s)
{{a}, {}}
>>> s.add('b')
>>> print powerSet(s)
{{b}, {b, a}, {a}, {}}
>>> s.add('c')
>>> print powerSet(s)
{{c}, {c, a}, {c, b, a}, {c, b}, {b}, {b, a}, {a}, {}}
To be honest, I don't know of much practical use for this function. It's just a good exercise.

Analyze the Efficiency

Start a new text document recursion.txt. (This is not a Python file; it's just a plain text file, to contain English prose. Do not submit your response in Microsoft Word format or any other weird format; just use plain text as produced by TextWrangler.) Put your name and the date at the top. For each of the four functions you've written, describe the time cost using big-O notation, and explain your reasoning. A couple of sentences per list function should be about enough; the powerSet function may require more explanation. You are not required to collect real timing data as in Assignment: Efficiency.

Submit Your Work

Submit your files recursion.py and recursion.txt electronically, as usual. Here are the grading criteria.