2012 May 27,
Carleton College, Spring 2012
Prof. Joshua R. Davis, , Goodsell 106B, x4473
This assignment is a sequence is disconnected exercises, intended to help you learn recursion. Simply, you will implement the following five functions recursively. Each function should call itself to do its work; you should not need to write or use any other helper functions. You may complete this assignment individually, or with one partner. Submit your work electronically, by Friday at the start of class.
Recall from Intro to Python, Part B that the game length of a game with Paul is the number of things that I say in the game.
# Computes the Paul game length. # Input: Positive integer. # Output: Positive integer. def gameLength(n):
In mathematics, the combination function choose(n, k) computes how many ways there are to choose k objects from a set of n objects. For example, choose(4, 2) is 6, because there are six ways to choose two objects from a set of four objects. (If our four objects are called A, B, C, and D, then we can choose A and B, A and C, A and D, B and C, B and D, or C and D.) There are a couple of trivial cases: choose(n, 0) is defined to be 1, and choose(n, n) is also defined to be 1.
In a math class, you may have learned that choose is related to factorials like this: choose(n, k) equals n! / (k! (n - k)!). Thus, we could implement choose using a factorial function, which we already have. However, factorials get big extremely rapidly. Python can handle large numbers pretty easily, but many programming languages can't, so it's good to have a way of computing choose that doesn't use factorials.
Here's another handy property of the choose function: choose(n, k) equals choose(n - 1, k) + choose(n - 1, k - 1). Use this property to implement the choose function recursively.
# Computes the combination function n! / (k! (n - k)!), # without computing any factorials. # Input: Nonnegative integer n. Integer k such that 0 <= k <= n. # Output: Positive integer. def choose(n, k):
This next function, listSum, will not be graded, but I recommend that you write it anyway, because it will make writing the following function, arraySum, easier. Write it recursively, of course.
# Returns the sum of two lists of numbers (of equal length >= 0). # If the lists are empty, then returns the empty list. # Input: List of numbers. List of numbers of the same length. # Output: List of numbers of the same length. def listSum(a, b):
An array of numbers is a rectangular grid of numbers, of some dimension. Let me explain, through some examples:
But arrays don't stop there. Here's a 3 x 2 x 3 grid — that is, a (3, 2, 3)-array:
[[[0, 1, 1], [1, -1, 4]], [[2, 1, 2], [3, 3, 1]], [[-5, -1, 3], [2, 2, 2]]]
By now you can probably see where I'm going: For any k integers n1, n2, ..., nk ≥ 1, an (n1, n2, ..., nk)-array is an n1 x n2 x ... x nk grid of numbers. Whenever you have two arrays of the same dimensions (n1, n2, ..., nk), you can add them entry-by-entry to get a new (n1, n2, ..., nk)-array. For example, here are two (1, 3, 2, 3)-arrays, and their sum, which is also a (1, 3, 2, 3)-array:
> > > first = [[[[0, 1, 1], [1, -1, 4]], [[2, 1, 2], [3, 3, 1]], [[-5, -1, 3], [2, 2, 2]]]] [[[[0, 1, 1], [1, -1, 4]], [[2, 1, 2], [3, 3, 1]], [[-5, -1, 3], [2, 2, 2]]]] > > > second = [[[[5, 2, 2], [1, -1, 7]], [[2, 0, 0], [3, 9, 4]], [[4, 4, 4], [2, 2, 2]]]] [[[[5, 2, 2], [1, -1, 7]], [[2, 0, 0], [3, 9, 4]], [[4, 4, 4], [2, 2, 2]]]] > > > arraySum(first, second) [[[[5, 3, 3], [2, -2, 11]], [[4, 1, 2], [6, 12, 5]], [[-1, 3, 7], [4, 4, 4]]]]
So your job is to implement this function:
# Returns the sum of two arrays of numbers. # If the arrays are empty, then returns 0. # Input: Array of numbers. Array of numbers of the same dimensions. # Output: Array of numbers of the same dimensions. def arraySum(a, b):
I was going to add a fifth problem, asking you to draw a fractal. But let's not. If you want to know more about drawing fractals recursively, then read the textbook, examine my examples, and read about fractals on Wikipedia.
Don't forget to test your functions thoroughly, and to follow the polishing guidelines described at the end of the Image Processing assignment (no extraneous code, demo section at end, etc.). Submit your work electronically, following the directions at our Technical Issues page, by the start of class on Friday. It will be graded according to these criteria: