Assignment 4
(Recursive functions)

In this assignment, your task is to compute the number of ways in which you can eat m Idlis in n days.

Part 1 (Credit: 70%)

Suppose that you have to eat at least one Idli per day, and you eat a whole number of Idlis on each day. Consider the function E(m,i,n) which stands for the number of ways you eat m Idlis from Day i to Day n. Suppose that you eat k Idlis on Day i. Then, the number of remaining possibilities is E(m-k,i+1,n). Now vary k. Also supply suitable boundary conditions.

Write a recursive function to implement E(m,i,n).

Report the output of your program for the following two inputs.

   m = 13, n = 10
   m = 32, n = 16

Remark: The answer is actually a simple closed-form expression given by the binomial coefficient C(m-1,n-1). Your algorithm must not make use of this formula. You need to employ the recursive approach as mentioned above.

Part 2 (Credit: 30%)

Repeat Part 1 with the added constraint that you are allowed to eat at most B Idlis per Day, where B is a positive integer to be supplied by the user.

You may write a new function for E(m,i,n) in this case. Alternatively, you may rewrite the function of Part 1 and pass B always to it. The value B = 0 implies that there is no limit on the number of Idlis that can be consumed per day (Part 1). For B >= 1, you consider the bound (Part 2).

Report the output of your program for the following two inputs.

   m = 13, n = 10, B = 2
   m = 32, n = 16, B = 8