CS 21: Homework #8

HW #8: Recursion, Recursion, and Recursion!

Due 11:59pm Tuesday, April 3

The program handin21 will only submit files in the cs21/homework/8 directory.

Your programs are graded on both correctness and style. Please review the comments regarding programming style on the main page

Some of the problems will have optional components that allow you to further practice your skills in Python. Optional portions will not be graded, but may be interesting for those wanting some extra challenges.

Recursion on lists

Complete each the following functions using a recursive solution. (You can find similar examples in the lectures directory from the beginning of the week.) Although it is not required, you may find it good practice to write iterative versions of these functions, too.

You should not use any of the methods in the list class (such as insert, append, remove, etc).

Complete all the functions from the practice.py program that we began working on in class. Be sure to copy that file to your cs21/homework/8 directory.
Write a function called multiplyList(lst) that takes a list of numbers (lst) and returns the product of all the numbers in the list. Return 1 if the list is empty. Save your implementation of multiplyList(lst) and the solution to all the other problems below in one file called recurse.py in your homework/8 directory.
Below are some test cases for the multiplyList function you will write. You should add some more test cases. They need not be exhaustive, but they should check more than just a few basic test cases. In subsequent questions, you will write most or all of the test cases yourself. You should put your tests in a separate function called test() which is started below. The assert statement checks to be sure that the statement is true, and if not, raises an AssertionError.
```
def test():
    """
    Tests the functions in this program.  Be sure to verify that the
    answer your are expecting is the answer you get by using the
    assert statement.  
    """
    
    #Here are some tests for question 2 to get you started.
    res = multiplyList([1, 2, -5, 3])
    assert res == -30

    res = multiplyList([])
    assert res == 1

    print 'All tests passed'
```
OPTIONAL DIFFICULT QUESTION: This problem may be challenging and is optional. Be sure to complete the required questions before attempting this one.
Write a new version of multiplyList(lst) called newMultiplyList(lst) which defines the product of an empty list to be 0. Be sure to write your own test cases. For example:
```
newMultiplyList([1, 2, -5, 3]) # returns -30
newMultiplyList([]) # returns 0
```
Write test cases for the functions you wrote in Question 1 using the style shown in above.
Write a function called addOne(lst) which returns a list which has each element of lst increased by one. For example:
```
addOne([]) # returns []
addOne([1, 2, -5, 3]) # returns [2, 3, -4, 4]
```

Write a function called insertBeforeFirst(match, insert, lst) which inserts an item (insert) into a list (lst) immediately before the first occurrence of a specified item (match). This function returns a list without changing the original list. For example:

# inserts 'pea' before the first 'pod' in ['a','green','pod']
# should return ['a', 'green', 'pea', 'pod']
insertBeforeFirst('pod', 'pea', ['a','green','pod'])

# inserts 'pea' before the first 'pod' in ['pod','pod','pod']
# should return res == ['pea', 'pod', 'pod', 'pod']
insertBeforeFirst('pod', 'pea', ['pod','pod','pod'])

# since there is no occurrence of 'pod', we do not insert 'pea'
# should return ['a','green','leaf']
insertBeforeFirst('pod', 'pea', ['a','green','leaf'])

Write a function called collapseFirstPair(lst) which locates the first time that the same symbol appears twice in a row in a list (lst) and removes one of them. Return a list with this pair removed, do not change the original list. Be sure to add your own test cases. Here is one to get you started:
```
# should return ['a', 'b', 'c', 'd', 'd']
collapseFirstPair(['a', 'b', 'c', 'c', 'd', 'd']) 
```
Write a function called collapseAllPairs(lst) which collapses all pairs found in a list. (As above, it returns a list and does not modify lst.) For an extra challenge, solve this by using the collapseFirstPair function you wrote above.
Here is an example:
```
# should return ['a', 'b', 'c', 'd', 'e', 'f']
collapseAllPairs(['a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'e', 'f', 'f'])
```
Write a function called swap(x, y, lst) that takes a symbol x, a symbol y, and a list (lst) and returns a list with all occurrences of x replaced by y and all occurrences of y replaced by x. Be sure to write your own test cases. For example:
```
# should return ['blue', 'fish', 'red', 'fish', 'blue']
swap('red', 'blue', ['red', 'fish', 'blue', 'fish', 'red']) 
```
Write a function called listReplace(pairlst, lst) that takes a list of pairs (pairlst) and a list (lst) and returns a list with the first element of each pair replaced by the second element of each pair. This problem is more difficult than it may initially seem. Be sure your function can handle both test cases below. (The second test case is the harder one.) Also, be sure to write your own test cases. For example:
```
listReplace([('carrots', 'peas'), ('fork', 'spoon')],\
            ['eat', 'your', 'carrots', 'with', 'a', 'fork'])
# returns ['eat', 'your', 'peas', 'with', 'a', 'spoon']


listReplace([('carrots', 'peas'), ('peas', 'potatoes')],\
            ['eat', 'your', 'carrots', 'and', 'peas'])
# returns ['eat', 'your', 'peas', 'and', 'potatoes']
# NOTE: THE ANSWER IS NOT: ['eat', 'your', 'potatoes', 'and', 'potatoes']
```
OPTIONAL (CONCEPTUALLY) DIFFICULT QUESTION: This problem may be challenging and is optional. Be sure to complete the required questions before attempting this one.
Suppose you wanted to write a function addTwo similar to the function addOne you wrote above. There are three ways you could do this:
1. You could copy your solution to addOne and replace the 1 with a 2. (This is a bad solution: what if you also wanted addThree?)
2. You could modify addOne(lst) to be addN(lst, n) so you'd never need to write addTwo or addThree. But if you really wanted addThree, it would just be this:
```
def addThree(lst):
    return addN(lst, 3)
```
  This is a much nicer solution, but it only works if you want to add things to the elements of the list.
3. The most generic solution would allow you to specify what you wanted to do to each element of the list by passing it the name of a function you'd like to perform on each element. This is exactly what you did when you passed a comparator function to sort, e.g. lst.sort(cmp=comparator).
To implement this solution, write a function called listmap(fn, lst) which takes a function (fn) and a list (lst) as parameters and returns a list where you have performed the fn on every element of the list.
Here is an example:
```
def plusOne(x):
    return x + 1

# should return [1, 2, 3]
listmap(plusOne, [0, 1, 2])
```
(Python has a built-in function called map which does exactly this! You can do help(map) for more information.)
OPTIONAL (CONCEPTUALLY) DIFFICULT QUESTION: This problem may be challenging and is optional. Be sure to complete the required questions before attempting this one.
Do help(filter) to find out about the built-in function filter, then implement it using a recursive solution. Call your version listfilter(fn, lst) You can ignore what happens if the first argument is None.

CS 21: Algorithmic Problem Solving

HW #8: Recursion, Recursion, and Recursion!