递归问题

递归的思想其实很简单， 就是可以将解原始问题分解成为解规模较小的同类问题。

简单地说， 如果一个算法间接或直接地调用自身， 则可以称这个算法是递归算法。

递归算法会由两部分组成： 递归调用 + 递归终止条件

先看个简单的例子：
阶乘大家都很熟悉：

n! = n × (n-1) * ... * 2 * 1 = n * (n-1)!

于是解决n的阶乘的问题就转变成了解决(n-1)的阶乘的问题了， 依次下去直到条件满足终止递归， 即 n = 0.

再看看比较经典的汉诺塔游戏：
X, Y, Z 三个塔， 初始时在X塔上有n个盘子从小到大依次从上而下叠加， 先需要借助Y塔移到Z塔上， 并且移动过程中不能有大盘在小盘上的情况出现。

好， 来分析一下这个问题：
如果n = 1， 也就是说只有一个盘子， 简单， 直接从X移到Z就可以了。
当n > 1时， 我们从第二个盘子开始分析， 而对于1号盘子我们已经成功的移到了目标塔Z上去了， 那剩下的就是将2号移到塔Z上去。 此时我们可以完全不考虑从3号到n号的盘子， 因为它们都比1好和2好大， 所以可以当作不存在。 这样的话， 问题就可以分解了：
初始问题：
1号盘子在目标塔Z上， 2号在X塔上， 需将2好从X塔移到Z塔上 -

hanio(2, fromX, toZ)

转换问题：

a) hanio(1, fromZ, toY)
b) move(2, fromX, toZ)
c) hanio(1, fromY, toZ)

这样一来规模为2的问题就转换成了两次规模为1的问题再加上一次移动。

同样， 当规模为n的时候， 也就是去解决两次规模为n-1的汉诺塔问题和一次移动。。。如此递归下去就okay啦。

再来看一个例子： 求出n个布尔(0 或 1)的所有组合
很容易知道结果是有 2*2*2*...*2 = 2^n 种组合。 而 2^n = 2*2^(n-1)
所以我们分析下：
1. 定义一个长度为n的数组arr
2. 当n=1的时候， arr[0] = 0, 或者 arr[0] = 1。 只有这两中可能， 然后这也是递归的终止条件， 所以此时遍历arr把每一个元素打印出来
3. 当n>1的时候， 实际上就是在n-1打印的基础上把第n位的值设置为0或者1就可以了

所以可以得出以下递归方法：

public class Recursive {

	public static void main(String[] args) {
		int num = 10;
		int[] b = new int[num];
		coding(b, num);
	}

	private static void coding(int[] b, int n) {
		if (n == 1) { // 这个是递归终止条件
			b[n - 1] = 0;
			out(b);
			b[n - 1] = 1;
			out(b);
		} else { // 递归调用
			b[n - 1] = 0; // 唯一要做的就是把第n个元素赋值， 其余的交给递归来处理
			coding(b, n - 1); // 递归
			b[n - 1] = 1;
			coding(b, n - 1);
		}
	}

	private static void out(int[] b) {
		for (int i = 0; i < b.length; i++)
			System.out.print(b[i]);
		System.out.println();
	}
}

总结：
递归的关键就是怎样把复杂问题分解成为多个相同的小规模问题进行解决。
每个level只需要做同样/相似的一件事情（比如汉诺塔中的move， 布尔组合中的set value）， 其余的递归调用， 最终结果在递归终止块来完成。。。。。。