GATE CS Mastery
Cheat sheets

GATE CS 2015 Set 2 · Programming in C

Question 21

NATPrinted as CS Q.111 markNo negative markingMedium (estimate)

Question

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 _____.

Official answer and solution
Official answer
51
From
Official GATE 2015 answer key

Solution

Unroll the recursive recurrence relation computed by the C function fun.

The function definition is:

  • Base case: fun(1) = 1.
  • For n>1n > 1:
fun(n)=1+∑k=1n−1fun(k)×fun(n−k).\text{fun}(n) = 1 + \sum_{k=1}^{n-1} \text{fun}(k) \times \text{fun}(n-k).

Calculate sequentially:

  • n=1n = 1: fun(1)=1\text{fun}(1) = 1.
  • n=2n = 2:
fun(2)=1+fun(1)×fun(1)=1+1×1=2.\text{fun}(2) = 1 + \text{fun}(1) \times \text{fun}(1) = 1 + 1 \times 1 = 2.
  • n=3n = 3:
fun(3)=1+fun(1)fun(2)+fun(2)fun(1)=1+(1×2)+(2×1)=1+2+2=5.\text{fun}(3) = 1 + \text{fun}(1)\text{fun}(2) + \text{fun}(2)\text{fun}(1) = 1 + (1 \times 2) + (2 \times 1) = 1 + 2 + 2 = 5.
  • n=4n = 4:
fun(4)=1+fun(1)fun(3)+fun(2)fun(2)+fun(3)fun(1)\text{fun}(4) = 1 + \text{fun}(1)\text{fun}(3) + \text{fun}(2)\text{fun}(2) + \text{fun}(3)\text{fun}(1)
fun(4)=1+(1×5)+(2×2)+(5×1)=1+5+4+5=15.\text{fun}(4) = 1 + (1 \times 5) + (2 \times 2) + (5 \times 1) = 1 + 5 + 4 + 5 = 15.
  • n=5n = 5:
fun(5)=1+fun(1)fun(4)+fun(2)fun(3)+fun(3)fun(2)+fun(4)fun(1)\text{fun}(5) = 1 + \text{fun}(1)\text{fun}(4) + \text{fun}(2)\text{fun}(3) + \text{fun}(3)\text{fun}(2) + \text{fun}(4)\text{fun}(1)
fun(5)=1+(1×15)+(2×5)+(5×2)+(15×1)\text{fun}(5) = 1 + (1 \times 15) + (2 \times 5) + (5 \times 2) + (15 \times 1)
fun(5)=1+15+10+10+15=51.\text{fun}(5) = 1 + 15 + 10 + 10 + 15 = 51.
Final answer

51

Common trap

Forgetting the initial int x = 1; that adds 1 to the summation for each recursive call.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2015 Computer Science and Information Technology (CS) Session 2
Question
21 of 65, printed as CS Q.11
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.