In this assignment we will write a recursive function to calculate what is known as the binomial coefficient. The binomial coefficient 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 coefficient 3 2 = 3 (1) Where the result of the binomial coefficient 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)

1 Notice that for the binomial coefficient order doesnt 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!(n i)! (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 defining a recursive relationship: n i = n 1 i 1 + n 1 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 definition of the binomial coefficient, 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 definition, and simply means that there is only 1 way of choosing no items from a set (e.g. you dont 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 find a typedef given to you in the starting .hpp template: 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 defined to be of type bitint. Why did we use the bigint? Well, the largest result from factorial that will fit into a regular 32-bit int is 12! = 479001600. By 2 using a 64-bit int, we can expand the maximum factorial we can calculate a bit, where 20! = 2432902008176640000 and this fits into a 64-bit integer. Then you will write two versions of the binomial coefficient to count combinations. One version will use one of your factorial functions to directly count the combinations, using the first 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.

1. Write a function called factorialIterative(). This function should take a single BIG integer (bigint) as its parameter n, and it will compute the factorial n! of the value and return it as its result (as a bigint). Write this functions using a loop (do not use recursion).

2. Write the factorial function again, but using recursion. Call this function factorialRecursive(). The function takes the same parameters and returns the same result as described in 1.

3. Write a function called countCombinationsDirectly(). This function will compute the number of combinations that result from choosing i elements from set of n items. The function should take two bigint values as its parameters n and i, which will be integers >= 0. The function should use the equation 3 above to directly compute the number of combinations. You should use your factorialRecursive() function to compute the factorials in this function.

4. Write a function called countCombinationsRecursive(). This function will also count the number of combinations of choosing i elements from a set of n items. However, you need to implement this calculation as a recursive function, using the general and base cases described above for counting combinations in equation 4 (general case) and equation 5 (base cases). Your function will take the same two bigint parameters as input n and i with values >= 0, and will return a bigint result.

You will again be given 3 starting template files like before, an assg-04.cpp file of tests of your code, and a BinomialFunctions.hpp and BinomialFunctions.cpp header and implementation file. As before, you should practice incremental development, and uncomment the tests in the assg-04.cpp file one at a time, and implement the functions in the order shown. If you implement your code correctly and uncomment all of the tests, you should get the following correct output: