python必背源代码汉诺塔递归代码

Noah
Noah
发布时间:2026-11-18| 8人浏览过
原创

提供Python汉诺塔经典必背递归源代码实现,详细解析递归三步分解原理、3阶移动步骤推导、函数调用二叉树及参数角色轮换机制,附完整运行示例与内联矢量架构图。

汉诺塔问题是掌握计算机递归算法的核心必经之路。用 Python 实现汉诺塔,其本质是把“将 n 个圆盘从源柱移动到目标柱”的大任务,拆解为“先腾挪前 n-1 个盘、移底盘、再回迁 n-1 个盘”的三个递归动作。本文提供标准且高频考察的 6 行必背核心源码,并给出逐行运行机制、3 阶移动步骤推导及函数调用二叉树图解。
python必背源代码汉诺塔递归代码
图 0:汉诺塔三柱模型与递归转移原理概览

一、汉诺塔经典 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 的问题”等价转化为三个有序的关键步骤:

  1. 腾出空间(递归降阶):要想把 A 柱最底层的第 n 个大盘移动到 C 柱,前提是 A 柱上的前 n-1 个小盘必须已经全部移开。而目标柱 C 要接纳大盘,其底部必须为空。因此,前 n-1 个小盘唯一的去处就是辅助柱 B。这对应第一次函数递归调用 hanoi(n - 1, source, auxiliary, target)。
  2. 落子定局(单步基石):当 n-1 个小盘都在 B 柱之后,A 柱只剩唯一的第 n 号最大盘,C 柱完全为空。此时直接执行一次单步输出 print(f"{source} -> {target}"),将第 n 号盘放置于 C 柱底部。因为它是所有圆盘中最大的,后续任何圆盘都可以压在它上面,该盘完成终身归位。
  3. 回迁合并(二次递归):大盘就位后,剩下的任务是把暂存在 B 柱上的 n-1 个小盘重新移回 C 柱。此时 A 柱空出来了,正好充当中转辅助柱。这对应第二次函数递归调用 hanoi(n - 1, auxiliary, target, source)。
python必背源代码汉诺塔递归代码
图 1:汉诺塔递归三步分解原理与职责关系图

三、以 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 上方,全部圆盘归位完成。
python必背源代码汉诺塔递归代码
图 2:3 阶汉诺塔 7 步物理转移操作时序全景图

四、递归调用树与形参角色轮换剖析

很多初学者在背诵或手写汉诺塔代码时,最容易产生疑惑的地方是:为什么递归调用里的字母顺序一会儿是 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 步)。

python必背源代码汉诺塔递归代码
图 3:hanoi(3) 递归二叉树展开与调用栈回溯映射图

五、编写注意事项与复杂度总结

避坑提醒:
  1. 基线条件必须显式 return:如果写成 if n == 1: print(...) 后面忘记加上 return,程序将继续向下执行并调用 hanoi(0, ...),迅速陷入无限递归,引发 Python 的 RecursionError: maximum recursion depth exceeded。
  2. 切勿死记固定柱名:代码内部打印的一定是形参变量(如 source 和 target),而不是写死的字符串 'A' 或 'C'。只有通过变量传递,不同层级的柱子角色互换才能正确生效。

算法复杂度指标

指标维度 理论复杂度 具体数值 / 表现 原理解释
时间复杂度 O(2n) 2n - 1 次基本操作 规模每增加 1,移动次数翻倍递增。当 n=64 时,需要移动约 1.84 × 1019 次,属于典型的指数级复杂度。
空间复杂度 O(n) 最大占用栈帧深度为 n 在任一时刻,系统栈保存的最大调用深度等于二叉树的高度 n,因此在内存空间方面开销极小。
python必背源代码汉诺塔递归代码
图 4:汉诺塔递归算法考点、三要素与复杂度全景总结图
相关专题:

免责声明:本文内容仅供参考,不代表本站观点。转载或引用请注明出处。

Python 相关产品和应用

全部下载
Selenium

Selenium

4.51.0 · Windows

用于浏览器自动化和 Web 测试的 Python 工具。

scikit-learn

scikit-learn

1.9.1 · Windows

常用 Python 机器学习算法与模型评估工具库。

Black

Black

26.10.1 · Windows

强调一致性的 Python 自动代码格式化工具。

Ruff

Ruff

0.17.1 · macOS

由 Rust 编写的高速 Python 代码检查和格式化工具。

pytest

pytest

9.1.1 · Windows

简洁而强大的 Python 自动化测试框架。

FastAPI

FastAPI

0.146.0 · Windows

高性能 Python API 框架,支持类型提示和自动接口文档。

Flask

Flask

3.1.3 · Windows

轻量灵活的 Python Web 应用框架。

Django

Django

6.1.2 · Windows

成熟的 Python Web 框架,适合构建内容站点和业务系统。

Spyder

Spyder

6.1.7 · Windows

面向科学计算与数据分析的 Python 集成开发环境。

SciPy

SciPy

1.18.1 · Windows

面向科学、工程和技术计算的 Python 算法库。