递归实现排列组合的问题
下列的程序计算了m个A，n个B可以组合成多少个不同排列的问题。

int f(int m, int n)
{
if(m==0 || n==0) return 1;
return f(m-1,n)*(n+m)/m; //能不能详细解释一下这一句的推导过程
}
据我所知：
不尽相异的元素的全排列公式：
(n+m)!/n!m!=(n+m-1)!/n!(m-1)!*(n+m)/m
所以f(m-1,n)==(n+m-1)!/n!(m-1)!是不是？怎么来的？


[解决办法]
这是三角递推算法。
你可以给定m,n，追踪这个递推过程。
[解决办法]
m个A，n个B可以组合成多少个不同排列的问题。

假设A是1,B是0这个问题就变成了,m+n位的二进制数字有多少?
而这个数字只需要考虑m个1,最大的数字是1全在高位,最小的是全在低位.

从最大数字开始搬动末位1到低位去,有n种搬法.
搬动第2个1时候,对于前边的n种,有(n-1)+(n-2)+...=等差数列X(n-1) 种
搬动第3个1时候,对于前边的等差数列,又有等差数列种
...
结束条件是:最小的是全在低位

以上已经形成了递推式:
一,每次操作和上一次操作有关;
二,有终止;

凡是递推式问题,都可以非递归写出程序的.
递推式很重要,生成排列,组合都利用了这个原理,变化无穷,威力无比!~~



[解决办法]
这样理解行不行，假设已经将m个A中的m-1个A，n个B排列好了，此时共有m+n个空位，对应f(m-1,n)/m种方法（这里涉及到从m个A中选m-1个的问题），在此基础上，将剩余的那个A插入那m+n个空位中就行了，也就是f(m-1,n)*(m+n)/m