Recurrence relations when function call is made inside loop

Question

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 :

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

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?

Answer 1

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$

Answer 2

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