[Solved]: Recurrence relations when function call is made inside loop

Problem Detail: 

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?

Asked By : Siddharth Thevaril

Answered By : Nehorai

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$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51858

3.2K people like this

 Download Related Notes/Documents