取球的組合問題一（遞歸）

1. 問題描述：在m個不同的球中取出n個球，問有多少種的取法？

2. 思路分析：

① 這個實際上是一個組合的問題，我們在高中的時候學習過組合公式：

 是以可以求解相應的階乘來進行求解

② 除了使用上面的求解階乘的方法來進行求解我們還可以使用遞歸來進行求解，但是怎麼樣使用遞歸來求解呢？

分析題目可以知道對于目前的球我們可以取出來也可以不取，是以這樣就存在着兩種的選擇，把這兩種選擇的結果最終加起來就是我們要求求解的結果

對于目前的球我們可以選擇不取，那麼我們就可以在剩下的m - 1球中來取出n個球，假如取得話我們可以在剩下來的m - 1個球中取出n - 1個球 這樣就可以遞歸求解下去，最終就可以求得我們需要的結果

③ 其實這也是深度優先搜尋的過程，對于目前的球我們可以取，也可以不取，那麼這樣就存在着兩個平行的狀态，然後遞歸求解下去，對于出口的設計我們可以這樣想，m和n都是在變化的，對于不取這個平行狀态那麼m這個參數最終是會和n相同的那麼接下來的所有球都是要取的，是以存在一種取法，對于取目前這個球這個平行狀态那麼我們最終n這個參數最終是會變成零的，這也是一種取法，是以對于有傳回值的遞歸我們需要結合題目和相關參數的變化來進行确定

在想的時候可以把其中的過程想象成二叉樹，分别遞歸左子樹和右子樹來進行求解

3. 代碼如下：

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		if(m < n) {
			System.out.println(-1);
			System.exit(0);
		}
		long res = f(m, n); 
		System.out.println(res);
		sc.close();
	}

	private static long f(int m, int n) {
		//實際上對于目前的球我們可以取也可以不取是以存在兩種平行的狀态
		if(n == m) return 1;
		if(n == 0) return 1;
		return f(m - 1, n) + f(m - 1, n - 1);
	}
}