Python递归实现汉诺塔:完整代码与逻辑详解
详细解析如何使用 Python 递归解决经典的汉诺塔问题。包含完整可运行代码、递归逻辑三步分解、调用树执行时序与复杂度分析。
汉诺塔(Tower of Hanoi)是经典的算法问题,核心目标是将位于起始柱上的若干大小不等的圆盘,依照特定规则完整迁移至目标柱。通过递归思想,不论圆盘数量多庞大,问题都能被统一抽象为三步子任务:先将上方所有圆盘借助目标柱移至过渡柱,再把最大的底部圆盘移至目标柱,最后将过渡柱上的圆盘借助源柱移回目标柱。本文将提供可直接执行的 Python 完整代码,并从递归拆解、执行时序与复杂度三个维度进行清晰剖析。
一、汉诺塔规则与递归拆解思想
汉诺塔问题设定有三根立柱,通常标记为 A(源柱)、B(辅助柱)和 C(目标柱)。在源柱 A 上从上到下按直径从小到大的顺序叠放着 n 个圆盘。移动必须严格遵循以下三条约束:
- 每次只能移动一根立柱最顶端的一个圆盘。
- 圆盘只能在三根立柱之间来回放置。
- 任何时刻,较大的圆盘都不得压在较小的圆盘之上。
如果尝试按每一步的具体落点去思考多个圆盘的移动,很容易陷入繁复的推演细节中。递归解法的核心在于宏观抽象:把 n 个圆盘整体看作“上面的 n - 1 个圆盘”与“最底部的第 n 号圆盘”。无论 n 是 3 还是 10,移动过程均可精准概括为三步操作:
- 前置转移:将 A 柱上方的
n - 1个圆盘借助 C 柱移动到 B 柱。 - 底盘就位:将 A 柱上剩下的唯一一个最大圆盘(第
n号圆盘)直接移动到目标柱 C。 - 后置归位:将 B 柱上的
n - 1个圆盘借助 A 柱移动到目标柱 C。
当 n = 1 时,问题达到基准条件(Base Case),无需任何辅助柱中转,直接将唯一的圆盘从源柱移动至目标柱即可完成退出。这一递归基准条件是整个算法终止的边界。
二、Python 完整代码实现
在 Python 中实现汉诺塔递归算法,函数的形参需要明确指定四个要素:当前处理的圆盘数量 n、起始柱 source、辅助柱 auxiliary 和目标柱 target。为了清晰观察执行过程并统计总操作步数,下面的代码引入了计数器与详细的移动输出。
def hanoi(n, source, auxiliary, target, step_counter=None):
"""
使用递归算法解决汉诺塔问题并打印移动路径。
参数:
n (int): 当前需要移动的圆盘数量
source (str): 起始立柱名称
auxiliary (str): 辅助立柱名称
target (str): 目标立柱名称
step_counter (list): 可选步数计数器 [当前步数]
"""
if step_counter is None:
step_counter = [0]
# 基准条件:仅剩一个圆盘时直接移动
if n == 1:
step_counter[0] += 1
print(f"步骤 {step_counter[0]:02d}: 将圆盘 1 从 {source} 移动到 {target}")
return step_counter[0]
# 第一步:将上面 n - 1 个圆盘借助 target 移动到 auxiliary
hanoi(n - 1, source, target, auxiliary, step_counter)
# 第二步:将第 n 个最大圆盘直接从 source 移动到 target
step_counter[0] += 1
print(f"步骤 {step_counter[0]:02d}: 将圆盘 {n} 从 {source} 移动到 {target}")
# 第三步:将 auxiliary 上的 n - 1 个圆盘借助 source 移动到 target
hanoi(n - 1, auxiliary, source, target, step_counter)
return step_counter[0]
if __name__ == "__main__":
disks = 3
print(f"=== 开始求解 {disks} 层汉诺塔问题 ===")
total_steps = hanoi(disks, source="A", auxiliary="B", target="C")
print(f"=== 移动完成,共执行 {total_steps} 步移动 ===")
在 Python 3 环境下直接执行上述脚本,终端中输出的示例结果如下:
=== 开始求解 3 层汉诺塔问题 ===
步骤 01: 将圆盘 1 从 A 移动到 C
步骤 02: 将圆盘 2 从 A 移动到 B
步骤 03: 将圆盘 1 从 C 移动到 B
步骤 04: 将圆盘 3 从 A 移动到 C
步骤 05: 将圆盘 1 从 B 移动到 A
步骤 06: 将圆盘 2 从 B 移动到 C
步骤 07: 将圆盘 1 从 A 移动到 C
=== 移动完成,共执行 7 步移动 ===
注意参数位置的动态转换:在递归调用时,立柱变量的传递位置至关重要。第一步调用中目标柱与辅助柱互换位置(source, target, auxiliary),第三步调用中源柱与辅助柱互换位置(auxiliary, source, target)。这是通过形参映射实现角色动态更替的关键逻辑。
三、以 3 阶汉诺塔为例的逐步推导
为了直观感受代码执行时三根立柱的状态变迁,我们以 n = 3 的完整移动流程为例进行细化跟踪。总共需要进行 2^3 - 1 = 7 次移动:
- 阶段一:清空底层阻碍(步骤 1~3)。首先将圆盘 1 移至 C,圆盘 2 移至 B,再将圆盘 1 移至 B。此时上方的 2 个圆盘成功转移至 B 柱,A 柱只留下底层最大的圆盘 3。
- 阶段二:核心基底就位(步骤 4)。直接将圆盘 3 从 A 移动到目标柱 C。自此,最大的圆盘已到达终点位置,并在后续步骤中永远不需要移动。
- 阶段三:将暂存盘归位(步骤 5~7)。圆盘 1 从 B 移至 A,圆盘 2 从 B 移至 C,最后将圆盘 1 从 A 移至 C。至此所有圆盘在 C 柱上按序排列。
四、递归调用树与调用栈执行流程
计算机在执行递归函数时,依赖系统内部的调用栈(Call Stack)来管理每一层的函数状态。每次发生函数调用,系统都会为新调用压入一个“栈帧”(Stack Frame),记录当前的局部变量与返回地址;当函数执行完毕后,栈帧弹出,程序回到上一层调用的中断点继续向下执行。
以 hanoi(3, 'A', 'B', 'C') 为例,整个程序的执行结构可以表示为一棵深度为 3 的二叉树。程序采用深度优先遍历(DFS)顺序依次展开分支:先顺着最左侧的分支向下钻研直至命中 n = 1 的基准条件并输出,返回后打印当前层的中间单步移动,再向右侧分支递归深入。
五、复杂度分析与边界注意事项
理解汉诺塔算法的性能表现与边界制约,对于在实际工程中合理使用递归结构具有重要意义:
1. 时间复杂度:$O(2^n)$
设移动 n 个圆盘所需的步数为 $T(n)$。根据递归算法的定义:
- 基准条件:$T(1) = 1$
- 递归方程:$T(n) = 2 \times T(n - 1) + 1$
递推展开可得:
$$T(n) = 2^1 T(n-1) + 1 = 2^2 T(n-2) + 2 + 1 = \dots = 2^{n-1} + 2^{n-2} + \dots + 1 = 2^n - 1$$
移动步数随圆盘数量呈几何级数爆炸。例如:当 $n = 10$ 时,需要移动 1,023 步;当 $n = 30$ 时,步数将达到 10.7 亿步;当 $n = 64$ 时,即使计算机每秒能执行 10 亿次移动,也需要约 584 年才能完成。因此,汉诺塔算法的时间复杂度严格属于指数级 $O(2^n)$。
2. 空间复杂度:$O(n)$
尽管函数总共会派生出 $2^n - 1$ 次调用,但在任何给定时刻,系统调用栈只保存从根节点到当前活跃叶子节点的一条完整路径。因此,调用栈所占用的最大内存空间与树的高度成正比,即最大栈帧深度等于圆盘数量 $n$。由于算法没有开辟额外的动态数组或矩阵,辅助空间复杂度为 $O(n)$。
3. Python 递归深度上限与堆栈溢出提醒
Python 解释器为了防止无限递归耗尽 C 语言层面的系统堆栈,默认设置了递归调用深度保护限制(通常为 1000)。我们可以通过以下代码确认并按需临时调整:
import sys
# 查询当前 Python 环境的最大递归限制
current_limit = sys.getrecursionlimit()
print(f"当前默认递归限制深度: {current_limit}")
# 如有必要可调整深度(非必要不建议盲目调高)
# sys.setrecursionlimit(2000)
对于汉诺塔问题而言,当 $n$ 达到 30 甚至 50 时,瓶颈绝非栈深度限制(因为 50 远小于 1000),而是时间复杂度导致的无法在有限时间内完成计算。理解这一点有助于准确定位递归程序的性能瓶颈到底源自计算耗时还是堆栈资源耗尽。
六、总结
递归算法解决汉诺塔问题的精妙之处,在于跳过了对细微单盘物理轨迹的逐个纠缠,直接确立宏观上的自相似子结构。掌握 hanoi(n, source, auxiliary, target) 过程中角色立柱的位置更替、基准条件的返回时机以及调用栈的执行时序,不仅能彻底攻克汉诺塔这一经典题目,更能建立起分析树形分治与复杂递归算法的核心思维体系。
本站声明
本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。













