四、汉诺塔问题
传说越南河内有一个寺庙，寺庙里有三根柱子，憎侣之间传言如果按照某个规定将64个盘子全部移动另外的柱子上，世界末日也就到了。事实证明，如果僧侣每一秒移动一个，大概需要5800亿年，当然这只是一个传说，这也是汉诺塔（Hanoi就是河内的意思）。
汉诺塔问题的描述：有三个柱子A、B、C，现在有n个盘子，需要从A柱转移到C柱，需要满足一下条件：
（1）每次只能移动一个盘子
（2）任何时候小盘子不能放在大盘子下边
（3）B柱可以用来零时存放盘子，但是依然要满足小盘子不能放在大盘子下边的条件
其实，这个游戏我们小时候都玩过，如果只有三个盘子这个游戏是很简单的，但是盘子数量一旦多起来就不是很好处理了：
我们以三个盘子为例，我们不妨简单的玩一下：
第一步
第二步
第三步
第四步
第五步
第六步
第七步
对于三个盘子的汉诺塔来说，还是比较简答的，但是盘子的数量如果增加一杯呢？
如果从递推的角度去思考这个问题，一定要理性的分析一下这个过程中的规律，才能下结论。
但是如果思维反转，用递归来思考呢？
我们要实现64个盘子的汉诺塔，那么要让63个的变成一个什么样子呢？
我们要做的就是将前63个移动到B柱，将第64个从A移动到C，此时最大号的盘子就转移成功了：
然后我们再将B柱的所有盘子移动到C柱就好了
通过这个问题，我们巧妙的将大的问题抽象成一个统一可复制的算法，而计算机最大的优势就在于快速的做出大量的重复性问题。
public class Hanoi { public static void main(String[] args) { hanoi(3,'A','B','C'); } /** * 解决n层汉诺塔问题的方法 * @param num 盘子的数量 * @param from 第1根柱子 * @param temp 第2根柱子 * @param to 第3根柱子 */ public static void hanoi(int num,char from, char temp,char to){ if(num < 1){ System.out.println("您输入的数字不合法！"); } if (num == 1){ System.out.println("将【"+ num +"】个盘子从【"+from+"】转移到【"+to+"】"); } else { //要解决n层汉诺塔的问题，可以将n个盘子分解成（n-1） 1 // 1、先处理n-1个盘子的汉诺塔问题，从from转移到temp， hanoi(num-1,from,to,temp); // 2、挪动盘子 System.out.println("将【"+ num +"】个盘子从【"+from+"】转移到【"+to+"】"); // 3、再处理一次n-1个盘子的汉诺塔问题，从temp转移到to， hanoi(num-1,temp,from,to); } } }
时间复杂度的计算：
用递归来解决汉诺塔问题是非常方便的选择，最后我们来分析一下汉诺塔问题的时间复杂度。 我们很容易得到汉诺塔问题的递推公式，64层汉诺塔，需要将63层的汉诺塔在A和B之间转换两次+最大的盘子移动一次：
f(n)={ 1,n=1 2f(n−1)+1,n>1
计算过程：
f(n)=2f(n−1)+1=2∗（2f(n−2)+1）+1=2∗2f(n−2)+3=2 （n−1）+(1+3+7+...)=2 n−1
舍掉常数项，所以汉诺塔问题的时间复杂度为O(2^n)。
五、树和图的遍历
树的遍历，其实本质也是一种递归：
public class RecursiveBinaryTree { public static class Node { public int value; public Node left; public Node right; public Node(int v) { value = v; } } // 先序打印所有节点 public static void Preorder(Node root) { if (root == null) { return; } System.out.println(root.value); Preorder(root.left); Preorder(root.right); } public static void Inorder(Node root) { if (root == null) { return; } Inorder(root.left); System.out.println(root.value); Inorder(root.right); } public static void Postorder(Node root) { if (root == null) { return; } Postorder(root.left); Postorder(root.right); System.out.println(root.value); } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); Preorder(root); System.out.println("====先序遍历===="); Inorder(root); System.out.println("====中序遍历===="); Postorder(root); System.out.println("====后续遍历===="); } }
使用递归对图进行深度优先遍历，它的结构和之前的栈可能有些不同：
// 使用递归遍历图 public static <T> void recursive(Vertex<T> vertex){ // 拿到顶点进行遍历操作 if(!vertex.visited){ System.out.println(vertex.t); vertex.visited = true; } // 看看当前的顶点时候有邻接节点，如果有执行相同错做 if(vertex.neighborList != null){ for (Vertex<T> tVertex : vertex.neighborList) { recursive(tVertex); } } }
