算法-递归

递归重点：

1、寻找相似性（可能需要主动构造）
2、参数设置（参数分配不相同，否则死循环）
3、出口设置
（每次调用的层次不同，注意返回的次序）

例子：取球问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package recursion;

public class GetBall {
//在n个球中，任意取m个（不放回），求有多少种取法
	static int count=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int k=getBall(10,3);
		System.out.println(k);
	}
	
	public static int getBall(int n,int m) {
		//假设有一个球被标记，则规模变成
		//1、被标记的球已取到，则还剩n-1,还需取 m-1,即f(n-1,m-1) 
		//2、被标记球一定不取，则需从剩下的 n-1 中取 m,即f(n-1,m)

		if(n<m) return 0;
		if(n==m) return 1;
		if(m==0) return 1;
		
		return getBall(n-1,m-1)+getBall(n-1,m);
	}
}