edited by
20,904 views
62 votes
62 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 ______.

edited by

12 Answers

Best answer
130 votes
130 votes

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

edited by
30 votes
30 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
18 votes
18 votes

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

8 votes
8 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
Answer:

Related questions

38 votes
38 votes
5 answers
2
36 votes
36 votes
6 answers
3
go_editor asked Feb 13, 2015
15,514 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.