Tower of Hanoi的理解

汉诺塔之前一直是知道过程，理解不了代码。直到今天在知乎上看到一种理解方式，一下子就懂了。
如何理解汉诺塔的递归？ - 郭风林的回答 - 知乎
https://www.zhihu.com/question/24385418/answer/128213752
作者：郭风林
链接：https://www.zhihu.com/question/24385418/answer/128213752
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

汉诺塔永远只有三步：

image image image image <noscript> image image image image image image

图中是最常见的五层(五珠)汉诺塔，
其实几层都是一样，这里设为n，
冰箱门永远是汉诺塔上面的m=n-1层。

那么问题来了，怎样把冰箱门打开？
即：怎样把图中的1至4号串珠从A柱移动到B柱？
（三根柱子从左至右依次为A、B、C，五颗串珠从小到大依次为1到5）

这又变成了一道m层汉诺塔的问题(m=n-1)。
你可以继续用把大象装冰箱分几步的思路
去考虑m层汉诺塔的解法。

推导下去最终就得到了一个两层汉诺塔该怎么移动的问题，

这个相信你闭着眼也知道该怎么搞了。

image.png

这个递归代码里面， if disk == 1就是最后只剩一个盘子，直接移动到dest. 然后我们打开冰箱门，也就是把上面四个盘子当作门，一起移动到spare柱；然后我们把大象放进去，也就是把最大的盘子直接放到dest; 最后关上冰箱门，也就是把四个盘子从spare移动到dest. 则完成整个过程。