"""Homework 7: Recursion""" """1) The number of partitions of a positive integer n is the number of ways in which n can be expressed as the sum of positive integers in increasing order. For example, the number 5 has 7 partitions: 5 = 5 5 = 1 + 4 5 = 2 + 3 5 = 1 + 1 + 3 5 = 1 + 2 + 2 5 = 1 + 1 + 1 + 2 5 = 1 + 1 + 1 + 1 + 1 Write a tree-recursive function part(n) that returns the number of partitions of n. Hint: Introduce a locally defined function that computes partitions of n using only a subset of the integers less than or equal to n. Once you have done so, you can use very similar logic to the count_change function from lecture. """ def part(n): """Return the number of partitions of positive integer n. >>> part(5) 7 """ "*** YOUR CODE HERE ***" """2) A mathematical function g is defined by two cases: g(n) = n, if n < 4 g(n) = g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3), if n > 3 Write a recursive function that computes g. Then, write an iterative function that computes g. """ def g(n): """Return the value of g, defined above, computed recursively. >>> g(1) 1 >>> g(2) 2 >>> g(3) 3 >>> g(4) 10 >>> g(5) 22 """ "*** YOUR CODE HERE ***" def g_iter(n): """Return the value of g, defined above, computed iteratively. >>> g_iter(1) 1 >>> g_iter(2) 2 >>> g_iter(3) 3 >>> g_iter(4) 10 >>> g_iter(5) 22 """ "*** YOUR CODE HERE ***" ###################### # OPTIONAL QUESTIONS # ###################### """3) A perfect number is defined as a positive integer equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The second perfect number is 28, because 1+2+4+7+14=28. Write a function next_perfect(n) that tests numbers starting with n and continuing with n+1, n+2, etc. until a perfect number is found. You will need to implement sum_of_factors as well. """ def sum_of_factors(n): """Return the sum of the factors of n less than n. A factor of a positive integer n is a positive integer that divides n evenly. >>> sum_of_factors(21) 11 >>> sum_of_factors(28) 28 """ "*** YOUR CODE HERE ***" def next_perfect(n): """Return the smallest perfect number greater than or equal to n. >>> next_perfect(7) 28 """ "*** YOUR CODE HERE ***" """4) Write an iterative function that computes the number of partitions of n. Hint: Try building the cache that would result from memoizing the part function you already wrote, but iteratively. """ def part_iter(n): """Return the number of partitions of positive integer n. >>> part_iter(5) 7 """ "*** YOUR CODE HERE ***" """4.5) Write a data-directed apply function that computes the area or perimeter of either a square or a rectangle. Note: This question was added Friday night 10/14, after hw7 was originally released. """ class Square(object): def __init__(self, side): self.side = side class Rect(object): def __init__(self, width, height): self.width = width self.height = height def apply(operator_name, shape): """Apply operator to shape. >>> apply('area', Square(10)) 100 >>> apply('perimeter', Square(5)) 20 >>> apply('area', Rect(5, 10)) 50 >>> apply('perimeter', Rect(2, 4)) 12 """ "*** YOUR CODE HERE ***" ##################### # EXTRA FOR EXPERTS # ##################### from operator import sub, mul """5) The Y-combinator The recursive factorial function can be written as a single expression by using a conditional expression (Python syntax not introduced in the notes). http://docs.python.org/py3k/reference/expressions.html#conditional-expressions >>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1))) >>> fact(5) 120 To write a recursive function previously, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact without giving it a name! Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements). The sub and mul functons from the operator module are the only built-in function required to solve this problem. Write your solution as a doctest by filling in the expression below. >>> (lambda n: YOUR_CODE_HERE)(5) 120 Hint: Googling Y-combinator will tell you the solution, so don't do that until you've tried to solve the problem yourself! """ """6) Lists with loops. The Rlist class (copied below) can represent lists with cycles. That is, a list may contain itself as a sublist. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> s[20] 3 This question has two parts: A) Write a function has_cycle that returns True if and only if its argument, an Rlist instance, contains a cycle. B) Write a function has_cycle_constant that has the same behavior as has_cycle but requires only a constant amount of space. Hint: The solution to B is short (~10 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around. """ def has_cycle(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle(t) False """ "*** YOUR CODE HERE ***" def has_cycle_constant(s): """Return whether Rlist s contains a cycle. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> s.rest.rest.rest = s >>> has_cycle_constant(s) True >>> t = Rlist(1, Rlist(2, Rlist(3))) >>> has_cycle_constant(t) False """ "*** YOUR CODE HERE ***" ##################### # CODE FROM LECTURE # ##################### class Rlist(object): """A recursive list consisting of a first element and the rest.""" class EmptyList(object): def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): args = repr(self.first) if self.rest is not Rlist.empty: args += ', {0}'.format(repr(self.rest)) return 'Rlist({0})'.format(args) def __len__(self): return 1 + len(self.rest) def __getitem__(self, i): if i == 0: return self.first return self.rest[i-1]