重温汉诺塔游戏的递归思想

2022-08-21 19:06 作者:28283844972_bili 0人读过 | 我要投稿

前几天逛b站的时候刷到了一个有关汉诺塔游戏与递归思想的讲解演示视频，我个人认为是目前为止b站上面，能够将汉诺塔递归思想讲解得最为直观和通俗易懂的视频。在这里贴上视频链接，可以自行去观摩一下：

在完整且反复地观看了几遍之后，我的心情久久不能平复，感叹自己当时在课堂上学习递归这一章节得时候，如果我的讲师能够拿着同等质量的演示课件给台下的学生授课，至少大家在初遇递归的时候多少能体面一些。

大多数人最初接触到递归原理，大概率是源自汉诺塔这个游戏，作为递归算法及其思想最为经典的案例，是通向递归世界的必经之路。可汉诺塔是如何利用递归，在严格遵守游戏规则的前提下，好似万剑归宗般地、有条不紊地走向游戏终点？尽管源码就呈现在眼前，大部分初学者也无法轻松理解汉诺塔的递归思想，我也不例外。事实上我对汉诺塔的递归思想不甚了然，过去我对递归的认知仅停留在斐波那契数列的递归思路（非常糟糕的例子），直到我打算重新审视汉诺塔递归原理，结合上述视频的讲解模型以及我个人的思考，重温其中所蕴含的递归思想。

其实初学者对汉诺塔递归思想的理解最大困难在于，一旦柱子上的圆盘数量超出“简单模式”的范畴，从直观角度来说，之后圆盘的移动次序、轨迹看起来就会比较“凌乱”，尽管汉诺塔本身存在一定的游戏规则，即把A柱上的带孔圆盘全部移到C柱上，并仍保持原有顺序叠好；每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一柱上，不过这样的游戏规则对于我们来说依旧是有很大的操作空间。此时我们的思维往往会更专注于尽可能多地移动圆盘以接近问题求解的终点，停留在一个较大的时空跨越尺度上，从而忽略将求解步骤拆分的思路。

所以何为递归？以我个人的理解，首先这是一种解决实际问题的有效手段，递归遵循固定步骤将一个问题规模由大到小、化繁为简地不断划分，逐步求解的过程，基本思想是分而治之。因此，再复杂的汉诺塔也脱离不了游戏框架本身，完全可以参考“简单模式”下汉诺塔的解题思路。

最简单的汉诺塔只有A柱上1个圆盘，思路也很简单，因为圆盘上方无其他圆盘阻挡，无需考虑其他圆盘的影响，直接将A柱上的圆盘迁移至C柱即可完成游戏；当圆盘数量增至2个时，这时需要在移动的过程中考虑到圆盘彼此之间的影响，不过思路依旧很简单，如图所示：

在此过程中，分别重新赋予ABC这三个柱子Src、Tmp、Dst别称，这有助于我们理解递归过程中圆盘的迁移轨迹，遵循上述迁移步骤，可以用最短的迁移次数达成目标。从剧透的层面来说，以上“三部曲”就是汉诺塔递归的基本思路（真的吗？我不信！），但又如何解释更多圆盘的例子呢？

原理基本类似，无论如何，为了能够保持原有排列顺序、移动全部的圆盘至终点，那么底层的圆盘就一定会比上层的圆盘先迁入终点，因此就需要每一层圆盘给相邻的下层圆盘让路，最极端的例子就是除最底层的大圆盘之外，其他上层圆盘均需要给它提前让路。

到这里问题就简化很多了，在每一轮迁移过程中，我们的目光仅需要放在当前圆盘以及它以上的圆盘部分就足够了。移动当前最底层的圆盘，就需要将其以上全部圆盘迁移至一个临时区域，然后恭迎当前圆盘入座终点，接着再把上层圆盘从临时区全部挪到终点便完事了，对照着来看不就是2层塔的迁移模式嘛？这种层层嵌套的形式让汉诺塔具备了递归的特性，即具有固定的操作步骤，问题规模可以从大到小不断划分。

由上述步骤可得，汉诺塔递归算法的伪代码如下：

此时新的疑问来了，关于Src、Tmp、Dst这三个参数，也就是ABC三个柱子的传入顺序貌似有些莫名其妙，不是太好理解。确实，关于传参顺序问题过去也是困扰我理解汉诺塔递归算法的拦路虎之一，但是如果结合n层汉诺塔的迁移步骤来看也不难理解，当前函数栈帧的传参顺序为Src (A)、Tmp (B)、Dst (C)，符合3根柱子初始状态的描述；假设 n > 1 ，紧接着的传参顺序是Src、Dst、Tmp，需要迁移的圆盘数量变为 n - 1 ，很明显对应的就是步骤1，所要表达的含义就是将除最下层以外的n-1个圆盘从Src迁移到Tmp，那么Tmp，也就是对应着的B柱，就是这 n - 1个圆盘的目标区域，因此原本的Dst位置就需要传入Tmp参数，同时Dst参数就充当临时区域传入原本的Tmp位置。MoveDisc对应的是步骤2，将最底层的圆盘从Src迁移到Dst终点处，这没什么好说的。同理可得最后的传参顺序Tmp，Src，Dst，意思就是将上层 n - 1个圆盘从Tmp迁移到Dst终点，此时，Tmp作为起点，Src充当临时区域。开头的演示视频中，采用的是调换柱子位置的方式来解释步骤3的传参顺序，其想要表达的意思是在迁移过程中，各个柱子所发挥的作用也在不断变化，因此需要我们及时更换视角。在此基础上，使用Src、Tmp、Dst作为ABC参数的别名，可以辅助我们更好地理解传参顺序的问题。

最后附上汉诺塔C程序执行效果：