CSC 15: Recursion Lab 1. Triangles. This problem asks you to write the recursive triangles program demonstrated in class. Read the comments at the beginning of the triangle.py skeleton program. 2. (Optional Challenge) A list/array in Python can contain nested lists. For example, with A = [2,[3,4],[[[5]]], [[2,7],[5,[6]]]] A[0] is 2, A[1] is [3,4], A[2] is [[[5]]], etc. The length of this list is 4. A[1][0] is the first element of A[1], namely 3. You can determine if something is a list/array using the 'isinstance' predicate. For example, isinstance([1,2],list) returns True and isinstance(4,list) returns False. Write a function to "flatten" a possibly-nested list such as A above into a one-level list. For example, flatten(A) should return the list [2,3,4,5,2,7,5,6] and flatten([2,[4,5,6,[7]]]) will return [2,4,5,6,7], etc .. Hint: think recursively. The program shouldn't be long. Remember also: A.append(x) adds new element x destructively to A. A = A+B : appends two *lists* A and B nondestructively: [1,2] + [3,4] == [1,2,3,4]. Careful: if A and B are both lists, then A.append(B) will create a list within a list: [1,2].append([3,4]) creates [1,2,[3,4]]. append and + work very differently. Run plenty of tests, like: print flatten([[2,3],4,[[5],[[[[6]]],7]]]) # should print [2,3,4,5,6,7] Usually nested lists are not more than 3-4 levels deep but your program needs to work for up to 998 levels of nesting. 3. Take the following recursive program: def r(x,y): if (x==0 or y==0): return 1 else: return r(x-1,y) + r(x,y-1) #r Estimate how much time it will take for r(40,40) to return. Hint: just waiting is not a good idea. 3b. (challenge) Write it more efficiently.