经典递归问题:取球问题

【请先食用上一篇】：[递归与循环]](https://www.jianshu.com/p/ebd9e232f044)

问：在n个球中，任意取出m个球(不放回)，求有多少种不同取法?

解法:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader scan=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("请输入球的总数：");
        int n=Integer.parseInt(scan.readLine());
        System.out.println("请输入取出球的个数：");
        int m=Integer.parseInt(scan.readLine());
        int count=f(n,m);
        System.out.println("在"+n+"个球中，任意取出"+m+"个球(不放回)，有:"+count+" 种不同取法");
    }
    private static int f(int n, int m) {
        if(m > n){
            return 0;
        }
        if (n == m) {
            return 1;
        }
        if (m == 0) {
            return 1;
        }
        return f(n-1,m-1)+f(n-1,m);
    }
}

运行截图：

image

思路：

【分析】：

递归问题，往往是将问题拆解成一个与原问题相似的问题+一个现阶段容易且能够解决的小部分，如图所示：

image

假设左边阶梯型图形为给出的问题，解法是转化为右边图形：将原问题拆解为与原问题相似的蓝色上部分以及现阶段容易且能够解决的绿色部分。

但有时候所给出的问题往往难以直接拆分，这类问题如同一个完美无缺的圆，突破口不易观察，很难直接将问题进行拆解，正如这道取球问题，这时就需要花点技巧。

image

【解决】：

我们假设n个球中有一个为幸运球，这时取球问题就出现了两种情况：

• 幸运球一定被取出:有了这个限定条件，相当于从n个球中拿出一个球(幸运球)事先放在取球者手中(这样才能保证幸运球一定被取出)，此时取球问题就变成了从n-1个球中取出m-1个球，即f(n-1,m-1)；
• 幸运球一定不被取出:有了这个限定条件，相当于从n个球中剔除出一个球(幸运球)，这样才能保证幸运球一定不被取出，此时取球问题就变成了从n-1个球中取出m个球，即f(n-1,m)；

综上，从n个球中取出m个球的总取法=取法1(幸运球被取出)+取法2(幸运球不被取出)=f(n-1,m-1)+f(n-1,m).

这便满足了递归问题两大要点之一:相似性，还需要满足另一要点:出口，如下：

1. if (m > n) return 0;//取球数>总球数，不合理，终止递归
   

2. if (n == m) return 1;//表示从x个球中取出x个球，只有一种取法
   

3.  if (m == 0) return 1;//表示从x个球中取出0个球，也是只有一种取法（即不取）
   

---