递归与循环：

理论上，任何循环都可以重写为递归形式。

1. 有时候，为栈限制，需要“尾递归”。
2. java不支持尾递归。

有些语言没有循环语句，只能使用递归。

循环改递归：

改为递归的关键是发现逻辑的“相似性”。

不要忘记递归的“出口”。

构造相似性：

1. 如果没有明显的相似性，需要主动构造。
2. 不能相似的原因很可能是缺少参数。
3. 递归与数学上的递推公式类似。

递归调用：

1. 递归调用紧紧是被函数恰为的函数。
2. 注意每次调用的层次不同。
3. 注意每次分配形参并非同一个变量。
4. 注意返回的次序。

示例1，求和：

public class ArraySum {

	public static void main(String[] args) {
		int [] a = {5, 2, 4, 3, 20};
		sum(a);
		System.out.println(f(a, 0));
	}

	//递归求和
	private static int f(int[] a, int begin) {
		if(begin == a.length) return 0;
		int x = f(a, begin+1);
		return x + a[begin];
	}

	//循环求和
	private static void sum(int[] a) {
		int sum = 0;
		for(int i = 0; i < a.length; i++)
			sum+=a[i];
		System.out.println(sum);
	}
}

示例2，字符串比较：

public class IsSameString {
	
	public static void main(String[] args) {
		String s1 = "abce";
		String s2 = "abcd";
		System.out.println(isSameString(s1, s2));
		System.out.println(f(s1, s2));
	}

	private static boolean f(String s1, String s2) {
		if(s1.length() != s2.length())
			return false;
		if(s1.length() == 0)
			return true;
		if(s1.charAt(0) != s2.charAt(0))
			return false;
		return f(s1.substring(1), s2.substring(1));
	}

	private static boolean isSameString(String s1, String s2) {
		return s1.equals(s2);
		
	}
}

经典的递归问题

组和问题：

题目：在n个球助中，任意取出m个（不放回），求有多少中不同的取法。

public class 组和问题 {
	public static void main(String[] args) {
		int k = f(10, 3);
		System.out.println(k);
	}

	private static int f(int n, int m) {
		if(n < m) return 0;
		if(n == m) return 1;
		if(m == 0) return 1;
		return f(n-1, m-1) + f(n-1, m);
	}
}

全排列问题：

题目：求n个元素的全排列。

public class 全排列 {

	public static void main(String[] args) {
		
		char [] date= "ABCDE".toCharArray();
		f(date, 0);
	}

	private static void f(char[] date, int k) {
		if(k == date.length) {
			for(int i =0; i < date.length; i++)
				System.out.print(date[i] + " ");
			System.out.println();
		}
		for(int i = k; i < date.length; i++) {
			//试探
			char t = date[k]; 
			date[k] = date[i]; 
			date[i] = t; 
			
			f(date, k+1);
			//回溯
		    t = date[k]; 
		    date[k] = date[i];
		    date[i] = t;	
		}
	}
}

最大公共序列：

题目：求两个串的最大公共子序列的长度。

public class 最大公共子序列 {
	public static void main(String[] args) 
	{
		int k = f("abc", "xbacd");
		System.out.println(k);
	}
	
	public static int f(String s1, String s2){
		if(s1.length() == 0 || s2.length() == 0)
			return 0;
		if(s1.charAt(0) == s2.charAt(0))
			return f(s1.substring(1), s2.substring(1)) + 1;
		else
			return Math.max(f(s1.substring(1), s2),
					f(s1, s2.substring(1)));
	}
}

求反串：

题目：求串的反转，如：abcd转换后为dcba。

public class 求反串 {

	public static void main(String[] args) {
		System.out.println(f("abcd"));
	}

	private static String f(String s) {
		if(s == null || s.length() < 2)
			return s;
		return f(s.substring(1)) + s.charAt(0);
	}
}

杨辉三角：

public class 杨辉三角 {

	public static void main(String[] args) {
		int n = 15;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= i; j++) 
				System.out.print(f(i, j) + " ");
			System.out.println();
		}
	}
	
	//杨辉三角m层的第n个元素
	private static int f(int m, int n) {
		if(n == 0) return 1;
		if(m == n) return 1;
		return f(m-1, n) + f(m-1, n-1);
	}
}

排列：

题目：3个A，2个B有多少种排列方法？

public class 排列组合 {
	public static void main(String []  args) {
		//3个A，2个B，有多少种排列方法
		System.out.println(f(3, 2));
	}

	private static int f(int m, int n) {
		if(m == 0 || n == 0) return 1;
 		return f(m-1, n) + f(m, n-1);
	}
}
//程序运行结果：10

整数的划分问题：

题目：如对正整数n=6；可以划分为：

• 6
• 5+1
• 4+2,4+1+1
• 3+3, 3+2+1， 3+1+1
• 2+2+2， 2+2+2+1， 2+1+1+1+1
• 1+1+1+1+1+1

public class 整数的划分 {

	public static void main(String[] args) {
		int [] a = new int[6];
		f(6, a, 0);
	}

	//对n进行划分
	//a[]: 缓冲
	//k:当前的位置
	private static void f(int n, int[] a, int k) {
		if(n<=0) {
			for(int i=0; i<k; i++) {
				if(i == k-1) {
					System.out.print(a[i]);
				}else
					System.out.print(a[i] + "+");
			}
			System.out.println();
			return;
		}
		
		for(int i=n; i>0; i--) {
			if(k>0 && i > a[k-1])
				continue;
			a[k] = i;
			f(n-i, a, k+1);
		}
	}
}