The following function computes the value of mCn correctly for all legal…
2006
The following function computes the value of
mCn
correctly for all legal values m and n (m≥1,n≥0 and m>n)
int func(int m, int n)
{
if (E) return 1;
else return(func(m -1, n) + func(m - 1, n - 1));
}
In the above function, which of the following is the correct expression for E?
- A.
(n = = 0) || (m = = 1)
- B.
(n = = 0) && (m = = 1)
- C.
(n = = 0) || (m = = n)
- D.
(n = = 0) && (m = = n)
Attempted by 40 students.
Show answer & explanation
Correct answer: C
Answer: The correct expression for E is (n == 0) || (m == n).
Explanation:
Base cases: If n == 0 then C(m,0) = 1. If m == n then C(m,m) = 1. These are the two conditions under which the binomial coefficient equals 1.
Recursive step: For 0 < n < m the function returns func(m-1, n) + func(m-1, n-1), which implements Pascal's identity C(m,n) = C(m-1,n) + C(m-1,n-1).
Why other expressions fail: Checking 'm == 1' is too narrow (it misses cases like C(5,5)). Using '&&' (AND) between conditions is too restrictive because it requires both conditions at once instead of accepting either base case.
Example: C(5,5) should return 1. '(n == 0) || (m == 1)' would not detect this, and any '&&' combination would also fail unless both parts happen to be true.