打印n层汉诺塔从最左边移动到最右边的全部过程

暴力递归就是尝试

1）把问题转化为规模缩小了的同类问题的子问题

2）有明确的不需要继续进行递归的条件(base case)

3）有当得到了子问题的结果之后的决策过程

4）不记录每一个子问题的解

补充一点，如果记录每一个子问题的解就是动态规划，后续文章会讲到。

递归方法

假设有3跟柱子，左、中、右，我们细分为如下三个步骤：

1）将1~N-1层圆盘从左 -> 中（大问题，需要继续划分为小问题）

2）将第N层圆盘从左 -> 右（base case）

3）将1~N-1层圆盘从中 -> 右（大问题，需要继续划分为小问题）

递归方法改进版

如果我们忘记柱子的左中右，将三根柱子标记为from、to、other。我们实现的是，将所有的圆盘（一共N层）从from -> to，同样细分为3个步骤：

1）将1~N-1层圆盘从from -> other（大问题，需要继续划分为小问题）

2）将第N层圆盘从from -> to（base case，可以直接打印）

3）将1~N-1层圆盘从other -> to（大问题，需要继续划分为小问题）

貌似没什么改进，因为还是细分这三步，同样要递归，但关键在于忘掉柱子的左中右顺序，只需要三个变量，代码可以少很多。

总结

汉诺塔问题还有非递归的解法，因为任何递归都可以改成非递归，只需要自己设计压栈。但是博主个人认为汉诺塔的递归方法比非递归更好容易理解和实现，非递归自己去设计压栈还比较麻烦，博主目前也还没弄懂，所以就只附上代码了。后面如果搞懂了在补充吧，