怎么打印Python汉诺塔递归的每一步移动详情

图 0：汉诺塔三柱模型与终端移动详情日志输出对应概览

一、汉诺塔递归的拆解逻辑与打印时机

汉诺塔问题规定：有三根柱子（通常记为 A、B、C），在 A 柱上自下而上按从大到小的顺序叠放着 n 个圆盘。目标是把所有圆盘完整移动到 C 柱，要求每次只能移动一个圆盘，且在移动过程中任何柱子上的大盘都不能压在小盘上方。

初学者在尝试用递归打印具体过程时，最常产生的困惑是“不知道该在代码的哪一行写 print 语句”。实际上，递归解决汉诺塔的本质并不是模拟一步一步挪动，而是将规模为 n 的大问题归纳分解为三个连续的逻辑阶段：

1. 腾空阶段：将 A 柱上方的前 n-1 个圆盘，借助目标柱 C，转移到辅助柱 B 上；
2. 核心动作：此时 A 柱仅剩底部的第 n 个大盘，且 C 柱上没有比它更小的盘压着，直接将第 n 盘从 A 柱移动到 C 柱——这正是打印动作发生的时刻；
3. 归位阶段：再将留在 B 柱上的 n-1 个圆盘，借助空出来的 A 柱，完整转移到目标柱 C 上。

只要在第二步处调用 print()，计算机就会在遍历整个递归树的叶子与分叉节点时，严格按照物理操作顺序输出每一次圆盘搬移动作。

图 1：汉诺塔递归核心三步分解架构与打印触发点

二、基础实现：打印源柱与目标柱的移动轨迹

在最简实现中，函数接收四个形参：n（当前要移动的圆盘数量）、source（当前起始柱）、target（当前目标柱）、auxiliary（当前辅助柱）。

当 n == 1 时，即构成了递归基底条件（Base Case），此时无需借助其他柱子，直接输出单步移动即可；当 n > 1 时，通过互换参数位置递归调用自身。

def hanoi_basic(n, source, target, auxiliary):
    # n: 当前子问题的圆盘数量; source: 起始柱; target: 目标柱; auxiliary: 辅助柱
    if n == 1:
        # 基底情形：仅剩一个圆盘，直接移到目标柱
        print(f"移动圆盘: {source} -> {target}")
        return

    # 步骤 1：把上面 n-1 个盘从 source 移到 auxiliary，借助 target
    hanoi_basic(n - 1, source, auxiliary, target)

    # 步骤 2：把第 n 个底盘从 source 移到 target
    print(f"移动圆盘: {source} -> {target}")

    # 步骤 3：把 auxiliary 上的 n-1 个盘移到 target，借助 source
    hanoi_basic(n - 1, auxiliary, target, source)

# 执行示例：移动 3 阶汉诺塔（从 A 移到 C，B 为辅助）
if __name__ == "__main__":
    print("--- 3阶汉诺塔基础移动步骤 ---")
    hanoi_basic(3, 'A', 'C', 'B')

运行上述代码后，终端将输出由内向外执行的完整动作：

这段输出完整展示了 7 次挪动。但这只是“柱子名称”的流动，在实际排查或演示时，往往无法分辨每次移动的究竟是哪一个圆盘，也无法直观统计执行到了第几步。

图 2：3阶汉诺塔7步操作时序与移动状态全过程跟踪表

三、进阶实现：带步骤序号与圆盘编号的详细追踪

要打印出“移动详情”，需要额外提供两项关键信息：全局递增的步数序号（第 X 步） 与 被移动圆盘的具体编号（第 k 号圆盘，规定 1 为最小盘，n 为最大盘）。

在递归函数中维护步数序号时，直接使用 Python 的全局变量 global step 容易造成代码耦合与状态污染。更安全规范的方式是使用类封装或闭包计数器（外层列表）。在打印圆盘编号时，步骤 2 中被移动的盘号恰好就是当前的 n。

class HanoiTracker:
    def __init__(self, total_disks, source='A', target='C', auxiliary='B'):
        self.total_disks = total_disks
        self.source = source
        self.target = target
        self.auxiliary = auxiliary
        self.step_count = 0
        self.history = []

    def solve(self):
        # 启动递归求解并打印统计
        self.step_count = 0
        self.history.clear()
        print(f"=== 开始求解 {self.total_disks} 阶汉诺塔 ({self.source} -> {self.target}) ===")
        self._recurse(self.total_disks, self.source, self.target, self.auxiliary)
        print(f"=== 搬移完成！累计执行 {self.step_count} 步，理论预期步数: {2**self.total_disks - 1} 步 ===\n")

    def _recurse(self, n, src, tgt, aux):
        if n <= 0:
            return
        
        # 1. 递归将上方 n-1 个圆盘从 src 移到 aux
        self._recurse(n - 1, src, aux, tgt)

        # 2. 物理搬移并记录当前第 n 号大盘
        self.step_count += 1
        record = {
            "step": self.step_count,
            "disk": n,
            "from": src,
            "to": tgt
        }
        self.history.append(record)
        
        # 格式化打印当前移动详情
        print(f"[步骤 {self.step_count:02d}] 移动圆盘 {n} : {src} ----> {tgt}")

        # 3. 递归将上方 n-1 个圆盘从 aux 移到 tgt
        self._recurse(n - 1, aux, tgt, src)

# 执行示例
if __name__ == "__main__":
    tracker = HanoiTracker(total_disks=3, source='A', target='C', auxiliary='B')
    tracker.solve()

执行该脚本后，输出信息条理分明，每个圆盘的生命轨迹一目了然：

图 3：递归调用树展开与形参/实参映射转换流程图

四、递归调用树与形参角色互换原理

许多开发者在阅读递归代码时容易迷失在形参名称里，误以为 target 永远代表固定的 C 柱。实际上，柱子的物理名称是实参，而其在函数定义中的角色是形参。

以调用 hanoi(3, 'A', 'C', 'B') 为例，其内部执行流程遵循中序遍历（In-Order Traversal）：

• 首次下钻：为了移动最底部的盘 3，必须先完成 hanoi(2, 'A', 'B', 'C')。在这次子调用中，'B' 占据了形参 target 的位置，'C' 沦为了形参 auxiliary。
• 再次下钻：为了移动盘 2，又必须先完成 hanoi(1, 'A', 'C', 'B')。到达基底，打印输出第 1 步：盘1 : A -> C。
• 回溯并打印：子函数弹出调用栈，回到 n=2 节点，输出第 2 步：盘2 : A -> B；紧接着调用右子树 hanoi(1, 'C', 'B', 'A')，输出第 3 步：盘1 : C -> B。
• 根节点执行：前两个盘全部整齐移至 B 柱后，根节点 n=3 终于获得执行机会，打印核心跨度：盘3 : A -> C。

参数在每次递归调用时发生的“旋转配对”，确保了无论规模多大，每一层递归都能准确感知当前的起点与终点。

图 4：汉诺塔递归打印常见错误排查与 2^n - 1 校验模型对照图

五、常见错误排查与理论校验准则

在编写与测试汉诺塔递归输出时，如果打印结果与预期不符，可根据以下几个具体表现进行排查：

1. 参数顺序传错导致死循环或大盘压小盘

2. 打印总步数与数学定理不匹配

数学上已严格证明，对于包含 n 个圆盘的汉诺塔，最优且合法的移动步数 M(n) 满足：

M(n) = 2ⁿ - 1

如果你的程序在执行 n=4 时打印出的步数不是 15 步，或者 n=5 时不是 31 步，说明基底条件或分支出现了逻辑漏判或重复触发。例如：同时写了 if n == 1: print(...) 和 if n > 1: ... print(...)，导致最底层的单步被多打印了一次。

3. 生成器（Generator）模式优雅解耦输出

在工业代码中，往往不希望算法核心函数内部强耦合 print()。利用 Python 的 yield 关键字，可以将移动动作逐个产出给调用方自由处理：

def hanoi_generator(n, source, target, auxiliary):
    # 通过生成器按需产生每一步移动详情元组 (disk_id, from_peg, to_peg)
    if n > 0:
        yield from hanoi_generator(n - 1, source, auxiliary, target)
        yield (n, source, target)
        yield from hanoi_generator(n - 1, auxiliary, target, source)

# 外部调用者自主决定打印格式或持久化
for step_idx, (disk, src, tgt) in enumerate(hanoi_generator(3, 'A', 'C', 'B'), start=1):
    print(f"序号 {step_idx}: 圆盘 {disk} 经由 [{src}] 转移至 [{tgt}]")

采用生成器后，算法本身保持纯粹无副作用，调用者既可以逐行实时在控制台打印，也可以将数千条历史存入文件或数据库，完美支持对复杂递归过程的细粒度监测。