python必背源代码汉诺塔递归代码
提供Python汉诺塔经典必背递归源代码实现,详细解析递归三步分解原理、3阶移动步骤推导、函数调用二叉树及参数角色轮换机制,附完整运行示例与内联矢量架构图。
一、汉诺塔经典 Python 递归核心源码
在 Python 中,解决汉诺塔问题不需要引入任何第三方库,直接使用标准解释器运行即可。函数的参数设计通常包含四个要素:当前需移动的圆盘数量 n、初始所在的源柱 source、需要送达的目标柱 target,以及作为中转桥梁的辅助柱 auxiliary。
# -*- coding: utf-8 -*-
# 汉诺塔经典递归实现(Python 3.6+ 标准运行环境)
def hanoi(n, source, target, auxiliary):
# 基线条件(Base Case):如果只有 1 个圆盘,直接从源柱移到目标柱并返回
if n == 1:
print(f"移动圆盘 1: {source} -> {target}")
return
# 第一步:把上面的 n-1 个盘子,从源柱移到辅助柱(此时 target 充当中转)
hanoi(n - 1, source, auxiliary, target)
# 第二步:把源柱最底下的第 n 个圆盘,直接移到目标柱
print(f"移动圆盘 {n}: {source} -> {target}")
# 第三步:把辅助柱上的 n-1 个盘子,移到目标柱(此时 source 充当中转)
hanoi(n - 1, auxiliary, target, source)
# 验证与调用示例:将 3 个圆盘从 A 柱移动到 C 柱(借助 B 柱)
if __name__ == "__main__":
print("--- 开始执行 3 阶汉诺塔移动指令 ---")
hanoi(3, 'A', 'C', 'B')
print("--- 移动完毕 ---")
执行上述测试代码后,控制台输出的完整移动序列如下:
--- 开始执行 3 阶汉诺塔移动指令 ---
移动圆盘 1: A -> C
移动圆盘 2: A -> B
移动圆盘 1: C -> B
移动圆盘 3: A -> C
移动圆盘 1: B -> A
移动圆盘 2: B -> C
移动圆盘 1: A -> C
--- 移动完毕 ---
可以看到,针对 3 个圆盘的情况,程序输出了恰好 7 行移动指令,每一步都符合“较小圆盘在上、较大圆盘在下”的规则约束。
二、核心原理拆解:把问题降解为三步递归
汉诺塔的规则十分严密:桌面上有三根柱子(A、B、C),所有圆盘最初由大到小叠放在 A 柱上;目标是将全部圆盘移动到 C 柱。移动期间必须严格遵守两条铁律:每次只能移动一个柱子最顶部的单盘,且在任意时刻,任何柱子上都绝对不能出现大盘压在小盘上方的情况。
直觉上如果试图一步步心算移动轨迹,当盘数增加时极易陷入混乱。递归之所以能够优雅地解决该问题,是因为它把“规模为 n 的问题”等价转化为三个有序的关键步骤:
- 腾出空间(递归降阶):要想把 A 柱最底层的第 n 个大盘移动到 C 柱,前提是 A 柱上的前 n-1 个小盘必须已经全部移开。而目标柱 C 要接纳大盘,其底部必须为空。因此,前 n-1 个小盘唯一的去处就是辅助柱 B。这对应第一次函数递归调用
hanoi(n - 1, source, auxiliary, target)。 - 落子定局(单步基石):当 n-1 个小盘都在 B 柱之后,A 柱只剩唯一的第 n 号最大盘,C 柱完全为空。此时直接执行一次单步输出
print(f"{source} -> {target}"),将第 n 号盘放置于 C 柱底部。因为它是所有圆盘中最大的,后续任何圆盘都可以压在它上面,该盘完成终身归位。 - 回迁合并(二次递归):大盘就位后,剩下的任务是把暂存在 B 柱上的 n-1 个小盘重新移回 C 柱。此时 A 柱空出来了,正好充当中转辅助柱。这对应第二次函数递归调用
hanoi(n - 1, auxiliary, target, source)。
三、以 3 个圆盘为例:7 步移动推导全过程
移动 n 个圆盘所需的最少步数具有严格的数学推导公式:2n - 1。对于 3 阶汉诺塔,总移动步数为 23 - 1 = 7 步。
下面梳理这 7 步具体是怎样在三根柱子之间交替推进的:
- 第 1 步(A ➔ C):将最小的盘 1 从 A 移到 C。A 柱剩余 [3, 2],C 柱为 [1]。
- 第 2 步(A ➔ B):将中等的盘 2 从 A 移到 B。此时 B 柱接纳盘 2,为后续叠放腾位。
- 第 3 步(C ➔ B):将盘 1 从 C 移到 B,平稳叠在盘 2 上方。至此,上层的 2 个圆盘完整迁移至 B 柱,完成了
hanoi(2, 'A', 'B', 'C')的整体任务。 - 第 4 步(A ➔ C):A 柱此时仅剩底部的盘 3,直接将盘 3 移动到目标柱 C。这是整个 3 阶移动的转折点与基石操作。
- 第 5 步(B ➔ A):为了腾出 B 柱上的盘 2,先把顶层的盘 1 转移回 A 柱暂存。
- 第 6 步(B ➔ C):将 B 柱上的盘 2 移动到 C 柱,压在底部的盘 3 上方。
- 第 7 步(A ➔ C):最后把暂存在 A 柱的盘 1 移动到 C 柱,压在盘 2 上方,全部圆盘归位完成。
四、递归调用树与形参角色轮换剖析
很多初学者在背诵或手写汉诺塔代码时,最容易产生疑惑的地方是:为什么递归调用里的字母顺序一会儿是 source, auxiliary, target,一会儿又是 auxiliary, target, source?
理解这一点的关键在于区分形参的位置语义与传入的实参角色:
- 函数签名为
def hanoi(n, source, target, auxiliary),第 2 个位置永远代表“起始柱”,第 3 个位置永远代表“目的地”,第 4 个位置永远代表“垫脚石”。 - 第一次递归调用
hanoi(n - 1, source, auxiliary, target):目标是把盘子运到辅助柱,因此在实参位置上,把代表辅助柱的变量传到了“目的地”位置,把代表目标柱的变量传到了“垫脚石”位置。 - 第二次递归调用
hanoi(n - 1, auxiliary, target, source):目标是把盘子从辅助柱运到目标柱,因此把辅助柱传到了“起始柱”位置,把源柱传到了“垫脚石”位置。
从函数调用的系统底层视角来看,整个计算过程形成了一棵严格的高度为 n 的满二叉树。控制台的每一次打印输出,实际上精确对应了这棵二叉树的中序遍历节点访问顺序(即:先遍历左子树完成第 1 到 3 步,再访问根节点打印第 4 步,最后遍历右子树完成第 5 到 7 步)。
五、编写注意事项与复杂度总结
- 基线条件必须显式 return:如果写成
if n == 1: print(...)后面忘记加上return,程序将继续向下执行并调用hanoi(0, ...),迅速陷入无限递归,引发 Python 的RecursionError: maximum recursion depth exceeded。 - 切勿死记固定柱名:代码内部打印的一定是形参变量(如
source和target),而不是写死的字符串'A'或'C'。只有通过变量传递,不同层级的柱子角色互换才能正确生效。
算法复杂度指标
| 指标维度 | 理论复杂度 | 具体数值 / 表现 | 原理解释 |
|---|---|---|---|
| 时间复杂度 | O(2n) | 2n - 1 次基本操作 | 规模每增加 1,移动次数翻倍递增。当 n=64 时,需要移动约 1.84 × 1019 次,属于典型的指数级复杂度。 |
| 空间复杂度 | O(n) | 最大占用栈帧深度为 n | 在任一时刻,系统栈保存的最大调用深度等于二叉树的高度 n,因此在内存空间方面开销极小。 |
本站声明
本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。













