The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+33 votes
5.3k 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 ______.

asked in Algorithms by Veteran (96.1k points)
edited by | 5.3k 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)

11 Answers

+64 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$

answered by Veteran (405k 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.
+1
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
+18 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
answered by Active (4.6k points)
0
Gd presentation ...
+10 votes

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

answered 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.....
+6 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
answered by Boss (11.9k points)
0
yes 51
+5 votes
Answer: 51.

Find the running code here: http://ideone.com/wrLiLm
answered by Boss (33.8k points)
edited by
+2 votes
Ans C)51

F(1)=1

F(2)=2

F(3)=6

F(4)=12

F(5)=51
answered by Boss (10.9k points)
+1 vote
Ans 51
answered by Boss (13.2k points)
0
How? please explain...
+1 vote
F(1) = 1

F(2) = 2

F(3) = 5

F(4) =15

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

Answer is 51.

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

answered by Active (2k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,080 answers
187,200 comments
70,990 users