Problem 1
The binomial coefficient, binom(n,m), occurs frequently in mathematics. This value can be computed recursively as follows:
binom(n,m) = binom(n-1,m) + binom(n-1,m-1), where 0 = m = n, binom(n,0) = 1, and binom(n,n) = 1.
Write a C program to compute binom(n,m) recursively. The values for n and m should be passed as command-line arguments with appropriate error checking.
Measure the execution time of your program as you vary the values of m and n. Plot this execution time as a function of n with different lines for various values of m. You should measure the execution time for each data point at least five times. Choose values of m and n such that your execution time ranges from less than a second to more than 30 seconds. What relationship do you see between m, n, and the execution time?
Problem 2.
Repeat Problem 1, but compute binom(n,m) iteratively, that is, without recursion. Measure the execution time of your program and compare the execution times of the two versions of the program. Which one is faster? Why?