Question

各位大神们，麻烦帮我解释一下这个递归是怎样推出来的？请详细解释一下推理过程，谢谢！！

计算3个A，2个B可以组成多少种排列的问题（如：AAABB, AABBA）是《组合数学》的研究领域。但有些情况下，也可以利用计算机计算速度快的特点通过巧妙的推理来解决问题。下列的程序计算了m个A，n个B可以组合成多少个不同排列的问题。请完善它。
int f(int m, int n){
if(m==0 || n==0) return 1;
return f(m-1,n)+f(m,n-1);
}

Answer 1

这个递归的意思可以用数学方法中的递推公式罗列出来
1.当m=0或n=0时，则，只剩下A或者只剩下B，这时候排列方式只剩下一种，为AAAA。。。或者BBBB....
2.当m>0&&n>0时，f(m,n) = f(m-1,n)+f(m,n-1)的意思可以这样理解：
分以下两种情况：

①从AB的组合中抽取掉一个A，这时候有f(m-1,n)种

②从AB的组合中抽取掉一个B，这时候有f(m,n-1）种。

不得不佩服写出这么优雅程序的人呀，当然，一切都建立在扎实的数学功底之上。

追问

2.当m>0&&n>0时，f(m,n) = f(m-1,n)+f(m,n-1)的意思可以这样理解：
分以下两种情况：

①从AB的组合中抽取掉一个A，这时候有f(m-1,n)种

②从AB的组合中抽取掉一个B，这时候有f(m,n-1）种。

这个能在详细一些吗？我还是没能理解

追答

f(m,n) = f(m-1,n)+f(m,n-1)。f(m,n）表示的是，当有m个A,n个b时候的排列的可能数，同样的，f(m-1)表示的是，当有m-1个A,n个b时候的排列的可能数，f(m,n-1）表示的是，当有m个A,n-1个b时候的排列的可能数.

假设我现在要求解有m个A,n个b时候的排列的可能数，我有两种选择：
1，从这堆AB的排列中拿掉一个A，然后求出拿掉一个A后的剩下的m-1个A和n个B的组合总数，也就是f(m-1,n);
2. 从这堆AB的排列中拿掉一个B，然后求出拿掉一个B后的剩下的m个A和n-1个B的组合总数,也就是f(n-1,m).
因为也就只有这两种不同的字母，我每次往前递推的时候也只能是选择拿掉其中一个字母，共有两种选择：拿掉A或者拿掉B。
所以最后f(m,n)的总可能排列数就是f(m-1,n)+f(m,n-1)，是两种可能情况的综合结果。