递归实践1——Cnm组合数计算


 1 #include <stdio.h>
 2 int f(int n,int m)
 3 {
 4     if(n<m){
 5         return 0;
 6     }
 7     if (n==m) {
 8         return 1;
 9     }
10     if (m==0) {
11         return 1;
12     }
13     return f(n-1,m-1) + f(n-1,m);
14 }
15 int main(int argc, const char * argv[])
16 {
17 
18     int n,m;
19     printf("从n个球中取出m个：");
20     scanf("%d,%d",&n,&m);
21     printf("%d
",f(n,m));
22     return 0;
23 }

//记得第一次用递归写组合数的时候用的方法是把n！用递归的方式计算下来，再套组合数的数学公式，现在想起来真的好无语。。。

看了辅导视频，感觉到递归的灵活性，于是试着按照视频讲解变换思路，用新的方法实现递归，我认为这样的方式更能体现递归的本质。

题目：从n个球中取出m个球，输入n,m 输出有多少种组合

思路：1.相似性：我们把所有可能的组合都放在操场上，设定一个球为特殊球，将组合中有特殊球的所有组合放在一起，没有特殊球的所有组合放在一起，再分别求出组合的个数。这样，我们使得每一步都有相似性，因而可以用递归的方法求出。2.设置出口：我们需要考虑n<m,n=m,m=0三种情况，这三种情况要分别返回0，1，1