Python打印汉诺塔每一步移动路径并编号计数

Mason

发布时间：2026-10-30 | 8人浏览过

原创

详细讲解如何在Python中实现汉诺塔递归算法，并为每一步圆盘移动记录并打印全局递增编号。包含递归状态传递、闭包可变对象与类封装三种实用方案及完整可运行代码。

在 Python 算法实践中，汉诺塔（Tower of Hanoi）是理解递归思想最直观的模型之一。标准的汉诺塔递归函数通常只需三四行代码即可完成路径打印，但若需要明确输出“第 1 步：A -> C”、“第 2 步：A -> B”这样的递增编号，初学者往往会遇到计数回退、重复计数或作用域错乱的问题。本文将剖析汉诺塔的递归运行轨迹，指出常见计数陷阱，并提供三种安全、清晰的全局编号计数方案与完整代码。

一、汉诺塔的递归逻辑与三步归纳法

汉诺塔问题的规则非常明确：有三根柱子分别标记为源柱（A）、目标柱（C）与辅助柱（B）。源柱上从大到小套着 $n$ 个圆盘，要求在每次仅移动一个圆盘、且任何大圆盘不得叠放在小圆盘上方的规则下，将全部圆盘完整迁移至目标柱。

将包含 $n$ 个圆盘的复杂任务拆解，核心在于递归的“自顶向下分解与自底向上归纳”。无论圆盘总数是多少，移动过程本质上都可以严格归纳为以下连续的三大动作：

前置归位：将上方编号为 $1$ 到 $n-1$ 的圆盘，以目标柱（C）作为中转辅助，整体移动到辅助柱（B）。
底盘转移：此时源柱（A）仅剩底部最大的第 $n$ 个圆盘，直接将其一步移动至目标柱（C）。
后续归位：将放置在辅助柱（B）上的 $n-1$ 个圆盘，以空出的源柱（A）作为中转辅助，整体移动至目标柱（C）。

图 1：汉诺塔递归算法的核心“三步拆解”模型

二、编号计数的逻辑难点与常见陷阱

很多开发者在初次尝试添加步骤编号时，最容易写出的错误方式是把整数 step 作为形式参数传入函数，并在调用时写成 step + 1：

# 常见错误写法：由于整数在 Python 中是不可变对象，递归回溯会导致计数倒退
def hanoi_wrong(n, source, target, helper, step=1):
    if n == 1:
        print(f"Step {step}: {source} -> {target}")
        return step + 1
    step = hanoi_wrong(n - 1, source, helper, target, step)
    print(f"Step {step}: {source} -> {target}")
    # 这里的 step 容易产生分支丢失，或需要在多层返回值中艰难传递
    step = hanoi_wrong(n - 1, helper, target, source, step + 1)
    return step

这种通过返回值手动传递整数的方式极其脆弱，一旦层级加深或返回值漏接，步数就会出现重号或跳号。其本质原因在于：汉诺塔递归遍历的是一棵二叉树，控制台打印发生在对树节点进行中序遍历的时刻。计数器是一个跨越整棵调用树各个分支的单调自增状态，必须保证所有递归分支引用的是同一个状态源。

图 2：3阶汉诺塔调用树与按时间线展开的全局计数节点

三、三种标准的编号计数实现方案

方案 1：列表可变对象引用计数（简单直观，首推方案）

在 Python 中，列表（List）属于可变数据类型。将计数器放在单元素列表 counter = [0] 中传入递归函数，所有递归层级共享同一个列表内存地址。每当执行实际打印操作时，直接将 counter[0] += 1。这种写法无需声明全局变量 global，作用域安全且逻辑简单。

def hanoi_with_list_counter(n, source='A', target='C', helper='B'):
    """
    使用可变列表共享计数状态的汉诺塔路径打印
    """
    counter = [0]  # 使用列表封装计数器，避免全局变量污染

    def _solve(k, src, dst, hlp):
        if k <= 0:
            return
        # 1. 将上面 k-1 个盘子从 src 移动到 hlp
        _solve(k - 1, src, hlp, dst)

        # 2. 移动第 k 个底盘，计数器自增并打印
        counter[0] += 1
        print(f"第 {counter[0]:02d} 步: 将圆盘 {k} 从 {src} 柱移动到 {dst} 柱")

        # 3. 将 hlp 上的 k-1 个盘子移动到 dst
        _solve(k - 1, hlp, dst, src)

    _solve(n, source, target, helper)
    return counter[0]

# 执行 3 阶汉诺塔测试
if __name__ == '__main__':
    total = hanoi_with_list_counter(3, 'A', 'C', 'B')
    print(f"迁移完成，累计执行步数: {total}")

控制台示例输出：

第 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

方案 2：生成器与 enumerate 组合（解耦算法与输出）

现代 Python 编程推崇“计算逻辑与展示逻辑分离”。通过将递归函数写为生成器（使用 yield），算法只负责依次产生每一次移动的具体元组 (圆盘编号, 源柱, 目标柱)，外部调用方直接借助内置函数 enumerate(..., start=1) 进行自增编号和自定义排版。

def hanoi_generator(n, source='A', target='C', helper='B'):
    """
    生成器实现汉诺塔每一步路径产出
    产出格式: (disk_number, source_peg, target_peg)
    """
    if n > 0:
        # 1. 递归产生前 n-1 个盘的移动路径
        yield from hanoi_generator(n - 1, source, helper, target)
        # 2. 产生当前第 n 个盘的移动路径
        yield (n, source, target)
        # 3. 递归产生剩余 n-1 个盘的移动路径
        yield from hanoi_generator(n - 1, helper, target, source)

# 调用与编号输出
if __name__ == '__main__':
    disks = 3
    print(f"=== {disks} 阶汉诺塔步骤清单 ===")
    for step_num, (disk, src, dst) in enumerate(hanoi_generator(disks), start=1):
        print(f"步骤 [{step_num}]: 圆盘 {disk} -> {src} 移向 {dst}")

提示：生成器方案具有优秀的惰性求值特性，当 $n$ 较大时不会在内存中提前构建巨大列表，适合流式写入日志或配合进度条展示。

方案 3：类封装（面向对象，多实例隔离）

在工程化项目中，若需要对移动过程做更多状态管理（如计算耗时、记录每根柱子的当前堆叠快照、支持重置等），使用类封装是最清晰的设计。

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

    def run(self):
        self.step_count = 0
        self.history.clear()
        self._move(self.n, self.source, self.target, self.helper)
        return self.step_count

    def _move(self, k, src, dst, hlp):
        if k <= 0:
            return
        self._move(k - 1, src, hlp, dst)
        
        self.step_count += 1
        record = (self.step_count, k, src, dst)
        self.history.append(record)
        print(f"Step {self.step_count:03d} | Disk {k} -> [{src}] to [{dst}]")

        self._move(k - 1, hlp, dst, src)

# 实例化执行
tracker = HanoiTracker(3)
total_steps = tracker.run()

图 3：3阶汉诺塔 7 步移动路径顺序总览

四、结果验证与步数数学规律

为了确认编号计数代码的正确性，可以通过数学归纳法推导出的总步数公式对结果进行验证。设 $S(n)$ 为移动 $n$ 个圆盘所需的总步数：

当 $n = 1$ 时，显然只需移动一次：$S(1) = 1$
当 $n > 1$ 时，根据三步拆解：$S(n) = S(n-1) + 1 + S(n-1) = 2 \times S(n-1) + 1$
递推可得闭式通项公式：$S(n) = 2^n - 1$

圆盘阶数 (n)	理论移动总步数 (2^n - 1)	Python 计算表达式	算法时间复杂度
1 阶	1 步	`(1 << 1) - 1`	O(2^1)
2 阶	3 步	`(1 << 2) - 1`	O(2^2)
3 阶	7 步	`(1 << 3) - 1`	O(2^3)
4 阶	15 步	`(1 << 4) - 1`	O(2^4)
5 阶	31 步	`(1 << 5) - 1`	O(2^5)
10 阶	1,023 步	`(1 << 10) - 1`	O(2^10)

边界与性能提示： 由于步数随阶数呈指数级（$2^n$）膨胀，当 $n \ge 20$ 时，总步数将超过 100 万步，在控制台大量打印（I/O 操作）会显著拖慢程序运行速度。在实际业务或测试中，若只需验证步数，应移除 print()，仅保留累加逻辑；若需要处理极大规模计算，注意 Python 默认最大递归深度限制（约为 1000），可通过 sys.setrecursionlimit() 进行调整。