write two recursive problems in Python. You have a couple of class periods and several nights to work on this, so be sure to plan accordingly. Each function is worth 5 points for a total of 10 points.

The third function will be worth extra credit and is not required. You can choose the two functions to complete.

There is an additional bonus problem at the end if you finish the required problems. This bonus, listOfWords, is not required.

These functions, still all recursive, deal with inputs and/or outputs that are not necessarily numeric.

Please put all of your functions for this problem in a single file called hw2.py. Thus, all of the parts of this problem will be submitted in a single file. Be sure to name your functions exactly as specified.

Note on what’s allowed here: Python is a very powerful language—fancy built-in functions like map, filter, split and strip (some of which we haven’t even discussed yet) would make this problem very simple, but would not support the underlying and fundamental idea of combining recursion with list processing. Your solution should not use any of these built-in functions, even if you know about them. Your solutions must instead be based only on “first principles”: recursion, if, elif, else, indexing and slicing, concatenation, and basic arithmetic operations.

• removeAll(e, L) takes in a list L and an element e (really any data whatsoever). Then, removeAll should return another list that is identical to L except that all elements identical to e have been removed. Notice that e has to be a top-level element to be removed, as the examples illustrate: >>> from hw2 import *

• >>> removeAll(42, [ 55, 77, 42, 11, 42, 88 ])

• [ 55, 77, 11, 88 ]

• >>> removeAll(42, [ 55, [77, 42], [11, 42], 88 ])

• [ 55, [77, 42], [11, 42], 88 ]

• >>> removeAll([77, 42], [ 55, [77, 42], [11, 42], 88 ])

• [ 55, [11, 42], 88 ]

•

Aside: It’s possible to write removeAll so that it works even if the second input is a string instead of a list, but you do not need to do this here.

• zipper(L, K) takes in two lists L and K and should output a single list of two-element sublists. Each of these two-element sublists should contain corresponding elements of L and K. If one of the two lists, L or K is longer than the other, the extra elements are discarded. For example: >>> from hw2 import *

• >>> zipper([], [1,2,3])

• []

• >>> zipper([1,2], [‘a’,’b’,’c’])

• [ [1,’a’], [2,’b’] ]

• >>> zipper([42]*3, [ ’tiles in scrabble’, ‘km in a marathon’ ])

• [ [42, ’tiles in scrabble’], [42,’km in a marathon’] ]

•

Aside: your zipper will probably work as-is with strings, if it works for lists.

• ind(e, L) takes in a sequence L and an element e. L might be a string or, more generally, a list. Then, ind should return the index at which e is first found in L. Counting begins at 0, as is usual with lists. If e is NOT an element of L, then ind(e, L) should return an integer that is at least the length of L. It can be len(L) exactly, as the example below returns, or any integer larger than that. >>> from hw2 import *

• >>> ind(42, [ 55, 77, 42, 12, 42, 100 ])

• 2

• >>> ind(42, range(0,100))

• 42

• >>> ind(‘hi’, [ ‘hello’, 42, True ])

• 3

• >>> ind(‘hi’, [ ‘well’, ‘hi’, ‘there’ ])

• 1

• >>> ind(‘i’, ‘team’)

• 4

• >>> ind(‘ ‘, ‘outer exploration’)

• 5

•

Bonus:

This problem is worth up to 2 bonus points. It is not required.

• listOfWords(S) takes as input a string S and should return a list of the “words” in S. By “words” we mean space-separated substrings of non-space characters. None of the “words” should be the empty string or contain a space. On the empty string listOfWords(”) should return the empty list. Consider these examples: >>> from hw2 import *

• >>> listOfWords(‘Bond. James Bond’)

• [ ‘Bond.’, ‘James’, ‘Bond’ ]

• >>> listOfWords(”)

• []

• >>> listOfWords(‘ ‘) # lots of spaces

• []

• >>> listOfWords(‘ Avada Ked… ‘) # more spaces

• [ ‘Avada’, ‘Ked…’ ]

•

(Hint: This problem is best handled by building several small recursive functions, each of which has a specific “mission”. Then, these functions can be used by listOfWords to do its job!)

The spiral function (10 points)

Write a function

spiral( initialLength, angle, multiplier )

that uses the turtle drawing functions to create a spiral that has its first segment of length initialLength and whose neighboring segments form angles of angle degrees. The multiplier will be a float that will indicate how each segment changes in size from the previous one. For example, with a multiplier of 0.5 each side in the spiral should be half the length of the previous side.

Base cases!

The spiral should stop drawing when it has reached a side length of

• less than 1 pixel or

• greater than 1000 pixels

Here’s a screenshot from the call spiral( 100, 90, 0.9 )

Remember that you will want to type mainloop() after calling spiral, e.g., spiral( 100, 90, 0.9 ); mainloop() – in order to release the window!

If you’d like to see the drawing in action, you can create the window, have a small pause, and then run the function and finish with mainloop(). You can separate all of these commands with semicolons. Here is an example (you only need import time the first time!

import time

shape( ‘turtle’ ); time.sleep(2); spiral( 100, 90, 0.9 ); mainloop()

The svtree function (15 points)

The idea here is to create a function that draws the side-view of a tree:

svtree( trunklength, levels )

Here is an example of the output from a function when svtree( 128, 6 ) is run:

and another example of the output when svtree( 50, 2 ) is run:

Note that these are really side view!

Calling left(90) before the call to svtree will yield a more traditional pose.

Hints

The key to happiness with recursive drawing is this: the pen must be back at the start (root) of the tree at the end of the function call! That way, each portion of the recursion “takes care of itself” relative to the other parts of the image.

One thing not to worry about is the number of branches (anything greater than 1 is OK), the exact angle of branching, the amount of reduction of the trunklength in sub-branches, etc. Design your own tree by making aesthetic choices for each of these.