3
$\begingroup$
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;
}

What is the value of fun(5)?

I find it difficult to realize a recurrence tree when the functions are called inside loops so I decided to go with the recurrence relations.

This is what I came up with :

enter image description here

However, the recurrence relation given in the solution book is slightly different:

enter image description here

I don't understand where I went wrong. I included 1 inside the summation since x loops with every iteration. So why is the 1 in the second equation outside?

$\endgroup$
  • $\begingroup$ ....fun$(5)=51$ $\endgroup$ – 3SAT Jan 14 '16 at 17:29
  • $\begingroup$ @Nehorai I already have the answer as I said, I need the explanation for the recurrence relation $\endgroup$ – Siddharth Thevaril Jan 14 '16 at 17:35
3
$\begingroup$

First, those two summation are not equivalet, the reason that the $1$ is outside is because this line in your code:

 int x=1,k;

Try to run this "by hand" and you will understand why you are addidng $1$ only once.

$\text{fun}(1)=1\\ \text{fun}(2)=2\\ \text{fun}(3)=5\\ \text{fun}(4)=15$

$$\Longrightarrow \text{fun}(n)=\begin{cases} 1;&&&&&&&&n=1\\ \color{red}1+\displaystyle\sum\limits_{k=1}^{n-1}\text{fun}(k)\times \text{fun}(n-k)&&&&&&&&n>1 \end{cases}$$


EDIT:

Step by step for n=3:

int fun (int 3)
{
  int x=1, k;
  if (3==1) return x;
  for (k=1; k<3; ++k)
     x = x + fun(k) * fun(3 – k);
  return x;
}

First loop $k=1:$

$x=\color{green}1+\underbrace{\text{fun(1)}}_{=1}\times \underbrace{\text{fun(3-1)}}_{=2}=\color{red}3$

Second loop $k=2:$

$x=\color{red}3+\underbrace{\text{fun(2)}}_{=2}\times \underbrace{\text{fun(3-2)}}_{=1}=\color{blue}5$

$\endgroup$
  • $\begingroup$ I'm only able to solve for fun(1) and fun(2) since even when n=2, the for() loop executes once. When n=3, I'm unable to figure out how it will calculate the value. Can you just explain me how it works for fun(3) step by step? I'll figure out the rest. $\endgroup$ – Siddharth Thevaril Jan 14 '16 at 19:28
  • 2
    $\begingroup$ @Sidsec9 I edited as you asked $\endgroup$ – 3SAT Jan 14 '16 at 21:10
  • 1
    $\begingroup$ I was able to solve too! Thanks for the edit! $\endgroup$ – Siddharth Thevaril Jan 15 '16 at 5:21
2
$\begingroup$

fun(1)=1

fun(2)=2

To understand, fun(3), just run the loop from k = 1 to 2.

At k = 1, fun(1) * fun( 3 - 1 ) will be called, whose values we already know are fun(1) and fun(2), i.e. 1 and 2 respectively.

At k = 2, fun(2) * fun( 3 - 2) will be fun (2) * fun(1), again which equal to 2*1 = 2;

So, adding them up, 1 + (1*2) + (2*1) = 1 + 2 + 2 = 5.

Similarly, try running the for loop within the limits and go on substituting the values of funs which you already know.

Similarly, for fun (4) will be , 1 + (fun(1)*fun(2)) + (fun(2)*fun(2)) + (fun(3)*fun(1)) = 1 + (1*5) + (2*2) + (5*1) = 15.

To understand the code, in the loop we can see that every time the loop runs, the value fun(k) * fun(n-k) is being added to previous value of x. Where x started from 1.

If you have to imagine a recurrence tree, every node whose value is n will have (n-1)*2 calls to fun as their children, except fun(1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.