CS19002 Programming and Data Structures Laboratory |
Spring 2009, Section 2 |

(Recursive functions)

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

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 functionE(m,i,n) which stands for the number of ways you eatmIdlis from Dayito Dayn. Suppose that you eatkIdlis on Dayi. Then, the number of remaining possibilities isE(m-k,i+1,n). Now varyk. 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 coefficientC(m-1,n-1). Your algorithm must not make use of this formula. You need to employ the recursive approach as mentioned above.

Repeat Part 1 with the added constraint that you are allowed to eat at mostBIdlis per Day, whereBis 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 passBalways to it. The valueB= 0 implies that there is no limit on the number of Idlis that can be consumed per day (Part 1). ForB>= 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