python汉诺塔:递归 + 算法可视化,把这道经典题真正搞懂

第一次看挺震撼，但仔细想想就会开始犯迷糊——程序是怎么知道每一步该移哪个盘子的？它没有提前列出步骤表，代码也没有写255步指令，就那么几行，它就知道了。

搞清楚这件事，才算真的把这段代码读懂了。

柱子为什么用栈来表示

翻开代码，最上面是一个 Stack 类：

classStack:def__init__(self):self.items = []defpush(self, item):self.items.append(item)defpop(self):returnself.items.pop()defpeek(self):ifnotself.isEmpty():returnself.items[len(self.items) -1]defsize(self):returnlen(self.items)

push 加到末尾，pop 从末尾取，peek 看末尾但不取——这就是个栈。

你想想实物里的柱子是怎么回事：盘子只能从顶上放，也只能从顶上拿，中间那些碰都碰不到。这个规矩和栈的规矩一模一样，所以柱子直接用栈来建模，省得自己再想一套约束逻辑。

程序里三根柱子就是三个栈：

defpole_stack():poles = [Stack() foriinrange(3)]returnpoles

poles[0] 左边，poles[1] 中间，poles[2] 右边。

初始状态把8个盘子按编号0到7压进 poles[0]：

foriinrange(n):poles[0].push(i)

0最先进，压在最底下，7最后进，在最顶上。盘子0是最大的，放底部；盘子7最小，放顶部。push 的顺序和视觉上的位置一对应，没有额外处理。

盘子的位置坐标怎么算出来的

这里有个设计挺巧的地方，第一次看代码可能不会注意。

创建盘子的时候，初始 y 坐标是这样定的：

plates[i].goto(-400, -90+20*i)

盘子0放在 y = -90，盘子1在 y = -70，依此类推，每个盘子间隔20像素往上堆。

三根柱子的 x 坐标是 -400、0、400，drawpole_3 里用 400 * (k-1) 算，k 取 0、1、2。

移动盘子的函数长这样：

defmoveDisk(plates, poles, fp, tp):mov = poles[fp].peek()plates[mov].goto((fp-1) *400, 150)plates[mov].goto((tp-1) *400, 150)l = poles[tp].size()plates[mov].goto((tp-1) *400, -90+20*l)

盘子先升到 y=150 的空中，平移到目标柱上方，再落下去。

落到哪个高度？-90 + 20 * l，l 是目标柱栈里当前有几个盘子。如果目标柱是空的，l=0，盘子落到 y=-90，就是最底部；如果目标柱已经有3个盘子，l=3，新盘子落到 y=-90+60=-30，刚好摞在第3个盘子上面。

和初始化时的公式是同一个，栈的深度直接就是落点高度，不用另外记录每根柱子当前有几个盘子。

移完之后更新栈的状态：

poles[toPole].push(poles[fromPole].pop())

从源柱弹出，压入目标柱。moveDisk 只管视觉上怎么画，这行才是数据上真正把盘子"搬过去"。两件事分开写，改其中一个不影响另一个。

第三步：递归——这才是核心

defmoveTower(plates, poles, height, fromPole, toPole, withPole):ifheight>= 1:moveTower(plates, poles, height-1, fromPole, withPole, toPole)moveDisk(plates, poles, fromPole, toPole)poles[toPole].push(poles[fromPole].pop())moveTower(plates, poles, height-1, withPole, toPole, fromPole)

四个参数：height 是当前要移动的盘子数量，fromPole 是源柱，toPole 是目标柱，withPole 是中转柱。

递归思路的关键，只有一句话：要移动最底下那个最大的盘子，必须先把上面所有的盘子搬走。

搬到哪里？中转柱。

搬走之后，底下那个大盘子就可以直接从源柱移到目标柱了。

大盘子到位之后，再把中转柱上那堆盘子搬到目标柱上去。

所以三步：

1. moveTower(height-1, from, with, to) —— 把上面 height-1 个盘子从源柱搬到中转柱，目标柱当中转

2. moveDisk(from, to) —— 把最大的那个盘子从源柱直接移到目标柱

3. moveTower(height-1, with, to, from) —— 把中转柱上那 height-1 个盘子搬到目标柱，源柱当中转

递归的终止条件是 height < 1，也就是没有盘子需要移动了，什么都不做，直接返回。

为什么这个逻辑是对的？

你可以用最简单的情况验证：

• 1个盘子：直接从源柱移到目标柱。✓

• 2个盘子：把小盘子先移到中转柱，把大盘子移到目标柱，再把小盘子从中转柱移到目标柱。✓

• 3个盘子：把上面2个盘子搬到中转柱（这又是一个2盘子问题），把最大的盘子移到目标柱，再把2个盘子从中转柱搬到目标柱（又是一个2盘子问题）。✓

规律很清楚：n 个盘子的问题，总能拆成两个 n-1 个盘子的问题，加上中间一次最大盘子的移动。

第四步：递归的代价——步数爆炸

n 个盘子需要移动多少次？

• 1个盘子：1次

• 2个盘子：3次（1次 + 1次 + 1次）

• 3个盘子：7次（3次 + 1次 + 3次）

• 4个盘子：15次

• n个盘子：2ⁿ - 1 次

公式是怎么来的？设 f(n) 是 n 个盘子的步数：

f(n) = f(n-1) + 1 + f(n-1) = 2 * f(n-1) + 1

解开来就是 f(n) = 2ⁿ - 1。

程序里 n = 8，所以要移动 2⁸ - 1 = 255 次。看着挺快，但如果是64个盘子，就是 2⁶⁴ - 1，大约是 1800 亿亿次，以每秒移一个盘子的速度算，得花5800亿年。

这就是指数增长的恐怖，汉诺塔问题的时间复杂度是 O(2ⁿ)。

第五步：为什么不用循环，非得用递归

有人会问，递归看起来这么绕，能不能用循环来写？

理论上可以，但代码会复杂很多，因为你需要自己维护一个调用栈来记录每层的状态。递归的本质就是让 Python 帮你管这个调用栈，代码看起来才这么干净。

汉诺塔这个问题的结构天然适合递归：问题本身就是由同类的更小的子问题组成的。把 n 个盘子的问题分解成两个 n-1 个盘子的问题，一直往下拆，直到拆到1个盘子，那是最简单的情况，直接解决。这种"大问题 = 若干小问题"的结构，就是递归最适合出手的场景。

整个程序的执行顺序

myscreen = turtle.Screen()drawpole_3()          # 画三根柱子n = 8plates = creat_plates(n)   # 创建8个盘子的 turtle 对象，初始放在左柱poles = pole_stack()       # 创建三个栈foriinrange(n):poles[0].push(i)       # 把盘子编号0~7压入左柱栈moveTower(plates, poles, n, 0, 2, 1)  # 从0号柱移到2号柱，1号柱中转myscreen.exitonclick()

moveTower 的最后三个参数：0 是源柱，2 是目标柱，1 是中转柱。改这三个数可以换起点和终点。

可以自己动的地方

改 n = 8 这个数字感受一下。改成4，速度快很多，可以肉眼跟上每一步；改成10，肉眼开始跟不上；改成15，等的时间就比较长了。

t.speed(100) 是 turtle 的速度，100是最快。改成1或者5，动画会慢下来，可以看清楚每一步盘子是怎么走路径的——先升起来，再平移，再落下去，这三段路径是在 moveDisk 里用三次 goto 完成的。

盘子颜色是随机生成的，每次运行都不一样，这是 random.randint(0, 255) 对 RGB 三个通道分别随机的结果。

最后

汉诺塔这个问题，递归解法的代码只有四行核心逻辑，但背后藏着一个很完整的思维框架：把一个无法直接解决的大问题，拆成若干个结构相同的小问题，直到小到可以直接解决为止。

这个框架不只是汉诺塔用，分治算法、树的遍历、快速排序，背后都是同一个逻辑。汉诺塔只是把这个逻辑用一个特别直观的物理模型展示出来。

程序里把递归过程可视化，配合栈来追踪每根柱子的状态，是一个很好的练习。看懂这段代码之后，再去看其他的递归问题，会顺很多。