题目： 

 

---

方法一：不讲武德法，注意：面试不能用！！ 

代码： 

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {//不讲伍德方法for(int x : A) C.add(x); }

---

方法二：

1.为什么可以用递归？ 

先看汉诺塔如果解决： 

 从图中看出：

处理N（盘子数）为1时候，其他数量少的情况比如 N=2，都可以由  N=1  的方式得来，就好像套娃：这个N=3 问题 可以分为，N=2来解决。

---

为什么可以用递归总结：

大问题-->相同类型子问题

子问题-->相同类型子问题;

大问题：把全部盘子借助B移动到C

子问题：把n-1个盘子，借助任何一个盘子移动到C(往复操作) 

---

2.怎样用递归：

首先要从宏观方面考虑，这个递归函数可以为我解决问题，不用纠结。 

其次就是设计递归函数： 

步骤一设计函数头：

找出重复子问题：这里X,Y,Z分别对应，A,B,C三个柱子，n盘子个数

void dfs(x, y, z,int n) 

 

步骤二： 设计函数体：
只要关心某个子问题在做什么即可，就是图中的(1,2,3)。

dfs(x,z,y,n-1);        //借助中间的z柱子，把x柱子上的n-1个盘子放到，y柱子上

 z.add(x.remove(x.size()-1));        //把x柱子的第一个剩下的盘子，放到z柱子

 dfs(y,x,z,n-1);        //借助X柱子，把y柱子上的n-1个盘子，放到z柱子上

 

步骤三： 

找递归出口: 这里就是，N==1时，把x柱子的第一个的盘子，直接放到z柱子 

---

代码： 

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A,B,C,A.size());}private void dfs(List<Integer> x, List<Integer> y, List<Integer> z,int n){//递归出口,只有一个盘子的时候，把x柱子上的盘子直接放到z柱子上if(n == 1) {z.add(x.remove(x.size()-1));return;}//任意一个子问题的具体步骤dfs(x,z,y,n-1);//借助中间的z柱子，把x柱子上的n-1个盘子放到，y柱子上z.add(x.remove(x.size()-1));//把x柱子的第一个剩下的盘子，放到z柱子dfs(y,x,z,n-1);//借助X柱子，把y柱子上的n-1个盘子，放到z柱子上}