汉诺塔部分核心内容来自《程序员的数学》一书。
图上这个游戏，名叫汉诺塔，不知道大家有没有玩过，传说印度教的创造之神大梵天在创造世界时顺手搞了三根柱子，在一根柱子上从上到下按小到大的顺序摞着一堆圆环，然后命令婆罗门把这些圆片全部移到另一根柱子，但是有一些规则，如下：
1.一次只能转移一个圆环到一根柱子上
2.圆环上面不能放比它小的圆环
戳这个网址试试吧：www.hannuota.cn/。三层是不是so easy，四层呢？五层呢？是不是就凌乱了，它的最少移动次数又是怎么计算出来的呢？
假设第一根柱子是起始柱，第二根为目标柱，第三根为中转柱。
让我们从只有一个圆环的情况开始吧。
只有一个圆环，那么只要把它移动到目标柱子就可以了，最少移动次数就是1步。
接下来是两个圆环。
因为小的圆环上面不能放大的，所以小圆环不能先移到目标柱上，否则大的放不了，那么就先把它移动到中转柱上，一步就搞定了，接下来把大的移到目标柱上，最后把小的移到目标柱上，最少次数为3次。
接下来是3个圆环。
移动方式如下图所示，最少次数为7次。
4个圆环的步骤图如下：
因为步骤较多一个图画不完，所以分两个图画，上面这个图的最后状态是上面三个圆环都移到了最右边柱子上，最大的圆环移到了中间目标柱上，所以接下来的步骤如下，总的移动次数为15：
仔细观察上述几个图，首先会发现最大的圆环都只移动了一次，从起始柱移到目标柱，其次是最大的圆环移动之前，剩余的圆环都完整的移动到了中转柱上，最后是最大的圆环移动之后剩余的圆环也都移到了目标柱上，所以除了最大的圆环剩下的圆环都完整的移动了两次，而如果忽略最大的圆环的话，那么其实会发现整个过程中是做两次n-1层汉诺塔，而解n-1层汉诺塔时如果再忽略最大圆环的话，就是做两次n-2层汉诺塔，这样一直下去，直到做一层汉诺塔，其实这就是个递归结构，那么可以归纳n层汉诺塔的解法如下：
设x为起点柱，y为目标柱，z为中转柱，n层汉诺塔即利用中转柱z将n个圆环从起点柱x转移至目标柱y。
1.n=0时：
没有圆环，不做任何动作；
2.n>0时：
首先，将n-1个圆环从x柱，经由y柱中转，移到z柱（解出n-1层汉诺塔）；
其次，将最大的1个圆环从x柱移到y柱；
最后，将n-1个圆盘从z柱，经由x柱中转，移到y柱（解出n-1层汉诺塔）；
将解出“n层汉诺塔”所需的最少移动次数表示为H(n)，那么有如下等式：
H(n) = 0，n为0的时候 H(n-1) + 1 + H(n-1)，n>0时
上述H(n)和H(n-1)的关系称为递推公式。
所以5层汉诺塔的最少移动次数：
H(5)=H(4) + 1 + H(4)=31 H(4)=H(3) + 1 + H(3)=15 H(3)=H(2) + 1 + H(2)=7 H(2)=H(1) + 1 + H(1)=3 H(1)=H(0) + 1 + H(0)=1 H(0) = 0
从下往上带入计算，即可求出5层汉诺塔的最少移动次数为31。
这里使用JavaScript代码来演示n层汉诺塔的解法和最少移动次数：
/*
函数参数依次为
n：汉诺塔的层数
x：起点柱
y：终点柱
z：中转柱
*/
let count = 0
function hanoi (n, x, y, z) {
if (n === 0) {
return ''
} else {
// 将n-1个圆环从x柱，经由y柱中转，移到z柱
hanoi (n - 1, x, z, y)
// 将最大的1个圆环从x柱移到y柱
console.log(`把当前${x}柱上最上面的圆环移动到${y}柱`)
count++
// 将n-1个圆盘从z柱，经由x柱中转，移到y柱
hanoi (n - 1, z, y, x)
}
}
hanoi (3, 'A','B','C')
console.log(`最少移动次数为：${count}`)
/*
输出：
把当前A柱上最上面的圆环移动到B柱
把当前A柱上最上面的圆环移动到C柱
把当前B柱上最上面的圆环移动到C柱
把当前A柱上最上面的圆环移动到B柱
把当前C柱上最上面的圆环移动到A柱
把当前C柱上最上面的圆环移动到B柱
把当前A柱上最上面的圆环移动到B柱
最少移动次数为：7
*/
有兴趣的可以对着这个步骤来移动汉诺塔，检验是否正确。
上面找规律来解决的方式是我在知道答案后的马后炮行为，只用来帮助更好的理解和解决汉诺塔这个游戏，并不具有通用性。
到这里就要有请另一个主角【递归】登场了，递归，就是自己调用自己。它通常用来把复杂的大问题层层转化为类似的小问题，先解决小问题再返回解决大问题的一种思想。
递归包含递和归两个步骤，要使用递归来解决一个问题首先要先判断该问题是否能分解成有相同思路的子问题，代码层面来说，就是是否能调用同一个函数来解决；其次是是否有边界条件，即分解到某一个子问题后发现不能再分解了，否则一直下去没有尽头，那就不叫递归了，叫永递，即永远的递下去（什么乱七八糟的）。其中递归函数里怎么继续再调用自身通常是需要找到一个大问题和小问题之间的联系的，也就是上面提到的递推公式，这是用递归来解决问题最难的部分，编写代码往往是很简单的。
但是不要怕，万事都有套路，解决递归问题的一般套路如下：
1.先定义一个函数，明确这个函数要干什么，具体的函数内容可以先不写；
2.寻找递归结束的条件，即当函数参数为什么时返回，不再继续调用自身，找到后在函数内写出来；
3.最重要的一步，找到问题和子问题间的联系，即找到递推公式，对于函数来说，也就是函数参数要怎么缩小，在函数内用代码表示出来。
搞定。
理论是简单的，接下来实践一下。
首先来看上一篇里提到的n的阶乘问题：n!=nn-1n-2.....21，很明显是符合递归特征的，比如5!=54!，4!=43!，所以一个大的阶层是可以分解成小的阶层来计算的，用上面的套路来用递归计算它。
1.定义一个函数
// 参数n为要计算几层阶层。
function jc(n) {}
2.寻找递归结束条件
通过上面的等式很明显知道n为1时就结束了，而1的阶层我们是知道的，为1。
function jc(n) {
if (n <= 1) {
return 1
}
}
3.寻找递推公式
上面也提过，5!=54!，4!=43!，抽象出来，即n!=n*(n-1)!，jc(n)是计算n的阶层，那么计算n-1的阶层为：jc(n-1)，这就是我们要的递推公式，用代码写出来。
function jc(n) {
if (n <= 1) {
return 1
}
return n*jc(n-1)
}
接下来再看一个斐波那契数列的问题，斐波那契数列是这样的一个数列：1、1、2、3、5、8、13、21、34....，求第n项的值是多少。
继续按套路来：
1.定义一个函数
// 参数n为要计算第几项。
function fb(n) {}
2.寻找递归结束条件
观察上面的数列，好像当n为1或2时都可以作为结束条件，确定不了，那么不妨先跳到第三步。
3.寻找递推公式
仔细观察上面的数列，发现从第3项开始每项的值都为前两项的和，即fb(n)=fb(n-1)+fb(n-2)，这就是递推公式，根据这个递推公式发现，n如果小于2就要计算第0项和负的项了，显然是没有的，所以第二步的结束条件也就找到了，n小于等于2时就可以结束了。
function fb(n) {
if (n <= 2) {
return 1
}
return fb(n-1)+fb(n-2)
}
最后来看一个排序的算法，快速排序，顾名思义，它很快，它为什么快呢，因为它的原理和二分法有点类似，不管什么排序，终归是要进行两两比较的，简单粗暴的方式就是每一个都和其他的进行比较，但是快速排序先根据一个中间数，根据比它大还是小来把整个数据分成两个部分，这样两个部分可以单独排序，最重要的是这两个部分里都只要内部进行比较就好了，不用再和另外一个部分进行比较，这样无疑就少了很多比较的过程，而分解成的两个部分又可以继续再分解成更小的部分，可以发现它是典型的递归结构，还是根据上面的套路步骤来：
1.定义一个函数
// 参数arr代表要进行排序的数字数组，如：[1,3,434,43,23,134,12,45]。
function quickSort(arr){}
2.寻找递归结束条件
很明显，当只有一个数时是不用排序的。
function quickSort(arr){
if (arr.length <= 1) {
return arr
}
}
3.寻找递推公式
因为首先是要找一个中间数，假设为n，那么最后排序完成的数组为quickSort(arr) = quickSort(比n小的数字组成的数组) 连接上n，再连接上比n大的数字组成的数组。翻译成代码如下：
function quickSort(arr){
if (arr.length <= 1) {
return arr
}
let middleIndex = Math.floor(arr.length / 2)
let middle = arr.splice(middleIndex, 1)
let leftArr = []
let rightArr = []
arr.forEach((item) => {
if (item <= middle) {
leftArr.push(item)
} else {
rightArr.push(item)
}
})
return quickSort(leftArr).concat(middle, quickSort(rightArr))
}
以上的示例都比较简单，而且也都还有优化的空间，包括递归本身的优化，及快速排序的优化，有兴趣的可以继续深入了解，咱们下次再会。
ps.汉诺塔的游戏开发教程已在路上，敬请期待。
参考资料：
1.《程序员的数学》第二版；
