从汉诺塔问题学习递归类问题的求解方法(只看这篇文章就够了）
（可忽略）背景：首先，关于标题的大言不惭，表示抱歉。目前，网上有很多关于汉诺塔求解的博文，我看了一些，感觉大致相同。首先都是圆盘移动的规律讲解了一下，然后贴上了解题代码。对递归的本质，没有进行深入的探究，可能也能解决当前的汉诺塔问题，但是给你一个新的递归类问题去解决，还是不行。在学习了imooc刘老师的课程后，对递归有了更清晰的认识，因此写此博文，总结递归类型问题的求解方法。希望看的人也可以有所收获，谢谢。
一 递归
本质上，递归是将原来的问题，转化为更小的同一问题
二 递归案例分析
此部分通过一个简单的案例：数组求和。来分析递归问题的求解过程，和递归函数一般的组成部分 (对递归很熟可以忽略，建议看)。
1 递归问题的解题思路分析
原问题：求解数组arr[0…n-1]中从索引0开始到索引n-1所有元素的和，即Sum(arr[0…n-1])；
将原问题转化为规模更小的同一问题，求从索引1开始到索引n-1所有元素的和，即Sum(arr[1…n-1])。然后用规模更小的问题的解去构建原问题的解，即
arr[0] + Sum(arr[1…n-1])。
上述过程一直重复，更小的同一问题，转化为更更小的同一问题，用更更小的同一问题去构建更小的同一问题的解。直到该问题不能被转化或分解成更小的问题，这里我们把该问题称为最基本的问题，即Sum([])
（总结）从上面递归问题的求解过程，我们可以得出解决递归问题的一般方法：找到最基本问题并给出基本问题的解；将原问题转换（或分解）成规模更小的同一问题，用规模更小的同一问题，去构建原问题的解。
2 代码编写的技巧
注意函数的“宏观”语义。即函数本身的功能，不要去过多的关注代码的执行过程！
以上都是刘老师相关课程的学习总结。下面正式开始用递归方式解决汉诺塔问题。
三 汉诺塔问题解决
1 问题描述
起源汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
抽象为数学问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。