Consider the following C function. int fun(int n) { int x=1, k; if (n==1)…
2015
Consider the following C function.
int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; }
The return value of fun(5) is ________.
Attempted by 40 students.
Show answer & explanation
Correct answer: 51
Answer: 51
Reasoning: Let C(n) denote the return value of fun(n). The function sets C(1)=1, and for n>1 it computes
C(n) = 1 + sum over k=1 to n-1 of C(k)*C(n-k).
C(1) = 1 (given).
C(2) = 1 + C(1)*C(1) = 1 + 1*1 = 2.
C(3) = 1 + C(1)*C(2) + C(2)*C(1) = 1 + 1*2 + 2*1 = 5.
C(4) = 1 + C(1)*C(3) + C(2)*C(2) + C(3)*C(1) = 1 + 1*5 + 2*2 + 5*1 = 15.
C(5) = 1 + C(1)*C(4) + C(2)*C(3) + C(3)*C(2) + C(4)*C(1) = 1 + 1*15 + 2*5 + 5*2 + 15*1 = 51.
Therefore, fun(5) returns 51.
A video solution is available for this question — log in and enroll to watch it.