In this assignment we will write a recursive function to calculate what is known as the binomial coecient. The binomial coecient is a very useful quantity, it allows us to count the number of combinations of selecting i items out of a set of n elements. For example, if we have 3 items A, B, C, there are 3 ways to choose 1 element from the items: choose A, or choose B or choose C. There are also 3 ways to choose 2 elements from the items: AB, AC, BC. There is only 1 way to choose 3 elements from a set of 3 items: ABC. When we choose 2 elements from a set of 3 items, we normally speak of this as counting the number of combinations of 3 choose 2, and mathematically we write this as a binomial coecient 3 2= 3 (1)

1 Where the result of the binomial coecient is to count up the number of combinations we will have for n items when we select i elements. As another example, just to make this clear, if we have a set of 4 items, ABCD, and we choose 2 elements from this set, we get: AB, AC, AD, BC, BD, CD = 6: 4 2= 6 (2) Notice that for the binomial coecient order doesn't matter, thus AB and BA are considered the same when choosing 2 elements from the set of 4, and we end up with only a count of 6 ways to choose 2 items from a set of 4 (look up permutations for a similar concept but where order matters). Mathematically we can compute directly the number of combinations for n choose i using factorials: n i= n! i!(ni)! (3) Where ! represents the factorial of a number, as we discussed in our textbook. However, another way of computing the number of combinations is by dening a recursive relationship: n i=n1 i1+n1 i (4) You can think of this as the general case of a recursive function that takes two parameters n and i, and computes the answer recursively by adding together two smaller subproblems. For this recursive denition of the binomial coecient, the base cases are: n 0=n n= 1 (5) We have already seen why n items choose n elements will always be 1. The other base case is used by denition, and simply means that there is only 1 way of choosing no items from a set (e.g. you don't choose). In this assignment we will write several functions. First of all you will write your own version of the factorial function. Actually I want you to write two versions, a recursive version of factorial, and a version that uses a loop (iterative version). We will be using long int (64-bit) instead of regular int (32-bit) for all of the parameters and return values. You will nd a typedef given to you in the starting .hpp template: 2 typedef long int bigint; A typedef like this is really just an alias or name for the other already known type. In this case bigint means a long int. All of your parameters and return values for the functions in this assignment should be dened to be of type bitint. Why did we use the bigint? Well, the largest result from factorial that will t into a regular 32-bit int is 12! = 479001600. By using a 64-bit int, we can expand the maximum factorial we can calculate a bit, where 20! = 2432902008176640000 and this ts into a 64-bit integer. Then you will write two versions of the binomial coecient to count combinations. One version will use one of your factorial functions to directly count the combinations, using the rst formula given above. Then your second version will be a recursive version, that uses the recursive general and base case given to implement counting the number of combinations. For this assignment you need to perform the following tasks.

C++