5.4k views

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

edited | 5.4k views
+1
option C 51??
+3
The code calculates this:

f(n) = 1 + $\sum_{i=1}^{n-1}f(i)f(n-i)$

where f(1) = 1 is the base case.

f(5) = 1 +  $\sum_{i=1}^{4}f(i)f(n-i)$ = 1 + f(1)f(4) + f(2)f(3) + f(3)(2) + f(4)(1)

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

by Veteran (416k points)
edited by
+5
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)
0
my dought started from f(3)

for k=1 we do 1+f(1)(2) next for k=2 isnt 1+f(2)f(1) ?
0
for, k = 2, f(2)* (f(1) will be added to the old value of x and old value of x is 1 + f(1) * f(2)
0
for k=2 , 2+ f(2) *f(1) , where n=3
0

Can you please explain why '1' is added to the summation in the recurrence relation?

+1
x = 1 and x is added to sum.
+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)\}$
0
yes, thats correct. But would give the same result- since f(x) is going recursively and adding "1".
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

0
Sorry. That statement was wrong. Actually it is

x = x + ...

So, only the initial value of x (=1) needs to be added and it is outside summation. Other sum, we are calculating.
0
IT GIVES SAME OUTPUT ...EVEN WHEN K++ instead ++K
0
Thats always the case in loop increment part, as the return value of it is not used anywhere.
0
Time complexity of above ??

Would it be O(n^n) ?
0
thank u sir ji
+1

@VS
time complexity should be Θ(3^n)

0
#Vishal Rotate the image  ...
0
How can they give such question for 1 marks.......it would take time around 5-7 min
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
by Active (4.6k points)
0
Gd presentation ...

Dont use tree method of recursion when they asked embedded function call inside loop . Better to do step by step like below:-

by Boss (23.4k points)
0
@rajesh nicely explain  but i m having doubt is it ++k and k++ gives the same value if yes plz tell me little bit about it . bcz i m thinking that we are not assign the value of k thts why its not making any effect on either k++ or ++k  ami rt??
0
k++ or ++k doesn't affrect ans.
0
superb sir ji.....
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
by Boss (11.9k points)
0
yes 51

Find the running code here: http://ideone.com/wrLiLm
by Boss (33.8k points)
edited
Ans 51
by Boss (13.3k points)
0
Ans C)51

F(1)=1

F(2)=2

F(3)=6

F(4)=12

F(5)=51
by Boss (11k points)
+1 vote
F(1) = 1

F(2) = 2

F(3) = 5

F(4) =15

F(5) = 51.
by (63 points)
0
Right
+1 vote
by Boss (13k points)

If you know the no of ways to split a number then you can easily solve the question:

5 can be split into (1,4), (2,3) (3,2)  (4,1)

therefore Fun(5) = 1+fun(1)*fun(4) + fun(4)*fun(1)+fun(3)*fun(2) + fun(2)*fun(3)

=  x+ 2*{fun(1)*fun(4) + fun(2)*fun(3)}

Similiarly

fun(2) = 1+ fun(1)*fun(1) = 2 ,since 2 can be split in 1,1

fun(3) = 1+ 2*{fun(1)*fun(2)} =5 ,since 3 can be split in 1,2 and 2,1

fun(4)= 1+ 2*{fun(1)*fun(3)}+fun(2)*fun(2) = 15 ,since 4 can be split in 2,2   1,3  and 3,1

fun(5)=  1+ 2*{fun(1)*fun(4) + fun(2)*fun(3)} = 1+ 2*(15+10) = 51

by Active (2.2k points)

1
2