# Recurrence relations when function call is made inside loop

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?

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

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$

• 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. Jan 14, 2016 at 19:28
• @Sidsec9 I edited as you asked
– 3SAT
Jan 14, 2016 at 21:10
• I was able to solve too! Thanks for the edit! Jan 15, 2016 at 5:21

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