组合数公式的递归实现，如何分析其时间复杂度？
递归形式实现的组合计数$C_n^r=C_{n-1}^r+C_{n-1}^{r-1}$
int C(int n,int r){
	if(n==r||r==0) return 1;
	else return C(n-1,r)+C(n-1,r-1);
}
请问这个时间复杂度是如何计算的?
答案是$$O(C_n^r)$$。

要得到这个答案，并不需要解递归方程。注意到递归只有在值为1的时候才结束，而最终的结果$$C_n^r$$由许多个这样的1相加而来，那么递归树是一棵有$$C_n^r$$个叶子结点的二叉树，总递归次数是树中所有结点的个数$$2C_n^r-1$$，即$$O(C_n^r)$$。

当然你要解递归方程也可以。设计算$$C_n^r$$需要的递归次数为$$T(n,r)$$，则有

$$T(n,r) = \left\\{ \begin{array}{ll} 1, & \text{if } n=r \text{ or } r=0 \\\T(n-1,r) + T(n-1,r-1) + 1, & \text{otherwise} \end{array} \right.$$

然后你发现这跟组合数的递推式本身非常相似，只是第二种情况中多了一个加1。

稍加变换，设$$S(n,r) = T(n,r) + 1$$，则有

$$S(n,r) = \left\\{ \begin{array}{ll} 2, & \text{if } n=r \text{ or } r=0 \\\S(n-1, r) + S(n-1, r-1), & \text{otherwise} \end{array} \right.$$

那个1就被吸收掉了。容易看出$$S(n,r) = 2C_n^r$$，故$$T(n,r) = 2C_n^r - 1$$。