Recurrence relations

Question

Consider the following function:

function X(n,r)

{

if(r==0 or n == r) then return 1;

else

return (X(n-1,r-1,) + X(n-1,r));

}

Find the worst case time complexity of function X ?

Comments

Is the recurrence relation T(n)=2T(n-1)+1 ??

---

@none30 Yes the recurrence relation will be this but can you explain how do we get this equation when 2 variables are involved? 

---

Basically I thought like this [I might be even wrong],
Given 2 variables, either one of them must be dominant
So, actually the recurrence relation will be like T(n)+T(r)=T(n-1)+T(r-1)+T(n-1)+T(r)+1
But, as mentioned in the previous comments n>r, which means T(n)>>>T(r)
So, I considered only T(n) and arrived at the recurrence relation

Answer 1

The recurrence relation is 

$T(n,r) = T(n-1,r-1) + T(n-1,r) +C$

This is the pascal’s recurrence relation. Basically program just calculates $nCr$ 
That is why N must be greater than R.
When you solve it, you will get $nCr$ and that will be the answers.

Now how to solve recurrence relations using 2 variables, use Generating functions → Topic of discrete maths, I guess.
So this question is one of those questions where you need to identify, something VERY specific. 
OR
use discrete math techniques to get to answer.

Comments

PS: I don't think they are going to give us 2 variable recurrence relations to solve in exam. If they give it will be something like this question, where there is a hint.