The Gateway to Computer Science Excellence

+41 votes

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

+91 votes

Best answer

$\text{fun}(1) = 1$;

$\text{fun}(2) = 1 + \text{fun}(1) * \text{fun}(1) = 1 + 1 = 2$;

$\text{fun}(3) = 1 + \text{fun}(1) * \text{fun}(2) + \text{fun}(2) * \text{fun}(1) = 5$;

$\text{fun}(4) = 1 + \text{fun}(1) * \text{fun}(3) + \text{fun}(2) * \text{fun}(2) + \text{fun}(3) * \text{fun}(1)$

$\qquad = 1 + 5 + 4 + 5 = 15$;

$\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)$

$\qquad = 1 + 15 + 10 + 10 + 15 = 51$;

More formal way:

The recurrence relation is

$f(n) = \begin{cases} 1, n = 1 \\ 1 + \sum_{i=1}^{n-1} f(i) \times f(n-i), n > 1 \end{cases}$

$f(1) = 1$

$f(2) = 1+ f(1).f(1)$

$\qquad = 1 + 1.1 = 2$

$f(3) = 1 + f(1). f(2) + f(2).f(1)$

$\qquad= 1+ 1.2 + 2.1 = 5$

$f(4) = 1 + f(1).f(3) + f(2).f(2) + f(3).f(2)$

$ \qquad= 1+ 1.5 + 2.2 + 5.1 = 15$

$f(5) = 1 + f(1).f(4) + f(2).f(3) + f(3). f(2)+ f(4).f(1)$

$\qquad = 1 + 1.15 + 2.5 + 5.2 + 15.1 = 51$

+8

select this for best answer :) I tried to drew the recursion tree for this which blew my mind in exam, so I couldn't solve it.

I should rather tried to figure out the recurrence equation, which I did but after the exam was over.

f(n) = 1 + summation k = 1 to n-1 f(k)*f(n-k)

I should rather tried to figure out the recurrence equation, which I did but after the exam was over.

f(n) = 1 + summation k = 1 to n-1 f(k)*f(n-k)

+2

Since 'x' is inside the loop, then shouldn't it be included in the summation?

I mean, why not write is as

$\sum \{1+f(i) \times f(n-1)\}$

I mean, why not write is as

$\sum \{1+f(i) \times f(n-1)\}$

0

0

Can you please explain how they might be equivalent? I solved it and the answers don't match

For example :

$\\ f(1)=1 \\ f(2) = 1+f(1).f(1) = 1+1.1 = 2 \\ f(3)=[1+f(1).f(2)]+[1+f(2).f(1)]=3+3=6$

In short :

$\sum \{1+f(i)\times f(n-i)\} = n+\sum \{f(i)\times f(n-i)\}$

This question is bothering me for a long time and I'm unable to understand only because of this small thing. Please help me understand this

+23 votes

fun(1) =1

fun(2) : x=1+fun(1)*fun(1)

x=1+1*1

x=2

fun(2) = 2

fun(3) : x = x+fun(1)*fun(2)

x= 1+1*2

x= 3

x= 3+fun(2)*fun(1)

x= 3+2*1

x= 5

fun(3) = 5

fun(4) : x = x+fun(1)*fun(3)

x= 1+1*5

x= 6

x = x+fun(2)*fun(2)

x= 6+2*2

x= 10

x = x+fun(3)*fun(1)

x= 10+5*1

x= 15

fun(5): x = x+fun(1)*fun(4)

x= 1+1*15

x= 16

x = x+fun(2)*fun(3)

x= 16+2*5

x= 26

x = x+fun(3)*fun(2)

x= 26+5*2

x= 36

x = x+fun(4)*fun(1)

x= 36+15*1

x= 51

+14 votes

+7 votes

don't use tree method of recursion when they asked embedded function call inside loop . let's do step by step

f(1) ⇒1

f(2) ⇒ x=1

1 + f(1)*f(1) = 2

f(3) ⇒ x=1

k=1 : 1 + f(1)*f(2) = 3

k=2 : 3 + f(2)*f(1) = 5

f(4) ⇒ x=1

k=1 : 1 + f(1)*f(3) = 6

k=2 : 6 + f(2)*f(2) = 10

k=3 : 10 + f(3)*f(1) = 15

f(5) ⇒ x=1

k=1 : 1 + f(1)*f(4) = 16

k=2 : 16 + f(2)*f(3) = 26

k=3 : 26 + f(3)*f(2) = 36

k=4 : 36 + f(4)*f(1) = 51

so 51

f(1) ⇒1

f(2) ⇒ x=1

1 + f(1)*f(1) = 2

f(3) ⇒ x=1

k=1 : 1 + f(1)*f(2) = 3

k=2 : 3 + f(2)*f(1) = 5

f(4) ⇒ x=1

k=1 : 1 + f(1)*f(3) = 6

k=2 : 6 + f(2)*f(2) = 10

k=3 : 10 + f(3)*f(1) = 15

f(5) ⇒ x=1

k=1 : 1 + f(1)*f(4) = 16

k=2 : 16 + f(2)*f(3) = 26

k=3 : 26 + f(3)*f(2) = 36

k=4 : 36 + f(4)*f(1) = 51

so 51

52,375 questions

60,572 answers

201,978 comments

95,388 users