GATE 2015 CS (CS2) – Question 24

Programming and Data Structures · Recursion · 1 mark · Numerical answer

Find fun(5).

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;
}

Show answer and explanation

Correct answer: 51

Explanation

Let F(n) be the returned value. F(1)=1 and F(n)=1+Σ F(k)F(n−k). Consequently F(2)=2, F(3)=1+2+2=5, and F(4)=1+5+4+5=15. Then F(5)=1+15+10+10+15=51.

GATE 2015 CS (CS3) Q38 – How many calls to get, including the initial and base-case calls, occur for get(6)?
GATE 2021 CS (CS2) Q33 – Find SomeFunction(15,255).
GATE 2021 CS (CS2) Q59 – What does this program print?
GATE 2026 CS (CS1) Q61 – Consider the recursive functions represented by the following code segment: The smallest…
GATE 2026 CS (CS2) Q61 – Consider the following ANSI C function. The maximum possible value that can be returned…
GATE 2025 CS (CS1) Q61 – The value printed by the given C program is . (Answer in integer)