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?