当前位置：首页 > article >正文

AI开发 - 算法基础递归的概念和入门（二）汉诺塔问题递归的应用和使用注意 - Python

article 2025/1/4 14:31:31

前面我们通过《AI开发 - 算法基础递归的概念和入门（一）递归算法的常见应用 PYTHON-CSDN博客》学习了递归的基础概念和常规的应用场景，其中有一个汉诺塔问题，有一些可玩的乐趣。今天我们在这里进一步通过这个问题来了解递归和递归的使用需要注意什么。

汉诺塔问题是一个经典的递归问题，非常适合用来学习递归的概念。我们从基础开始，一步一步讲解。

1. 汉诺塔问题简介

汉诺塔问题是一个著名的数学谜题，问题的描述如下：

有三个柱子，分别叫做 A、B、C。
某个柱子（比如A柱子）上有若干个圆盘，圆盘的大小是不同的，并且最小的圆盘在最上面，最大的圆盘在最下面。
任务是将这些圆盘从柱子 A 移到柱子 C，移动时必须遵循以下规则：
1. 每次只能移动一个圆盘。
2. 每次只能将一个圆盘从上面拿走，且只能放在空柱子或者比它大的圆盘上。
3. 要求在移动过程中，柱子 B 作为辅助柱子，可以帮助转移圆盘。

2. 递归思路解析

递归的关键是将大问题分解成更小的子问题。对于汉诺塔问题来说，假设我们要移动 n 个圆盘，从柱子 A 移到柱子 C，我们可以采取以下步骤：

第 1 步：先将上面 n-1 个圆盘从柱子 A 移到柱子 B，借助柱子 C。
第 2 步：将第 n 个圆盘（即最大的那个）从柱子 A 移到柱子 C。
第 3 步：再将 n-1 个圆盘从柱子 B 移到柱子 C，借助柱子 A。

这个过程会一直递归下去，直到 n=1，即只剩一个圆盘时，它就可以直接从 A 移到 C。

3. 编写递归函数

递归的核心是要有一个停止条件。对于汉诺塔问题，停止条件是当 n = 1 时，直接移动这个唯一的圆盘。

我们用 Python 来实现这个递归过程：

# 递归函数，移动 n 个圆盘
def hanoi(n, source, target, auxiliary):
    # 递归停止条件：只有一个圆盘时，直接移动
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    
    # 第 1 步：将 n-1 个圆盘从 source 移到 auxiliary，使用 target 作为辅助
    hanoi(n-1, source, auxiliary, target)
    
    # 第 2 步：将第 n 个圆盘从 source 移到 target
    print(f"Move disk {n} from {source} to {target}")
    
    # 第 3 步：将 n-1 个圆盘从 auxiliary 移到 target，使用 source 作为辅助
    hanoi(n-1, auxiliary, target, source)

# 测试函数：假设有 3 个圆盘
hanoi(3, 'A', 'C', 'B')

4. 解释代码

hanoi(n, source, target, auxiliary) 是递归函数，参数的含义是：
- n：要移动的圆盘数。
- source：源柱子（即要移出圆盘的柱子）。
- target：目标柱子（即圆盘要移到的柱子）。
- auxiliary：辅助柱子（即第三个柱子，用来暂时放置圆盘）。
当 n == 1 时，表示只有一个圆盘，这时直接将圆盘从 source 移到 target。
当 n > 1 时，先递归地将上面 n-1 个圆盘从 source 移到 auxiliary，然后再将最大的那个圆盘（第 n 个圆盘）从 source 移到 target，最后递归地将 n-1 个圆盘从 auxiliary 移到 target。

5. 运行结果

假设有 3 个圆盘，运行结果如下：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

这表示：

将第一个圆盘从 A 移到 C。
将第二个圆盘从 A 移到 B。
将第一个圆盘从 C 移到 B。
将第三个圆盘从 A 移到 C。
将第一个圆盘从 B 移到 A。
将第二个圆盘从 B 移到 C。
将第一个圆盘从 A 移到 C。

6. 递归思维要点

每次递归会将问题规模减小，直到问题足够简单（只有一个圆盘）。
递归调用的栈会自动处理好每一层的操作，并返回到上一层继续操作。
递归的本质是“分而治之”，每一层都在解决小规模的子问题。

7. 递归的优缺点分析

汉诺塔问题的递归算法具有非常清晰和直观的结构，但在实际应用中也存在一些优缺点。我们来逐一分析它的优缺点。

- 1. 优点

代码简洁易懂：递归算法是将问题分解成更小的子问题，非常符合汉诺塔问题的结构。代码简洁，逻辑清晰，易于理解。只需要遵循“移动 n-1 个圆盘”、“移动最大圆盘”、“再移动 n-1 个圆盘”的思路，就可以完美解决问题。
自然表达问题：汉诺塔问题本身就是一个递归问题，因此递归解法非常自然地契合了问题的结构。没有复杂的迭代和状态管理，递归本身就能很好地解决问题。
理论优雅：递归的思想与数学和理论计算机科学中的分治法相符合，能够很好的展示递归的基本思想：通过将大问题拆解为小问题来解决。这种方法在很多计算问题中都有广泛应用。
节省代码量：相较于使用迭代方法，递归算法通常能写得更简洁。避免了手动管理循环变量和栈操作，递归通过系统的调用栈来管理这些状态。

- 2. 缺点

性能问题（时间复杂度高）：
- 递归算法的时间复杂度是指数级别的，具体来说是 O(2^n)。这是因为每次递归都会处理两个子问题，每个子问题的规模是原问题的一半，直到递归到最底层（n = 1）。
- 这意味着对于大量的圆盘，算法的运行时间会非常长，随着 n 的增加，运行时间呈指数增长。
空间复杂度高：
- 递归算法会消耗较多的内存空间，因为每一次递归调用都会将当前的函数状态（如参数、局部变量等）压入系统的调用栈中。当递归的层数很深时，可能会导致栈溢出（StackOverflowError）。
- 空间复杂度是 O(n)，即递归的最大深度与 n 成正比。
示例：
- 如果 n 非常大（比如 1000 或更多），系统的栈可能就会溢出。
  
  这就是在笔记本上跑50个盘，崩溃了！
  实际上我跑这个case是通过vscode的jupyter notebook 远程连接到服务器上运行的，服务器很强大，占用内存如下：（不要轻易长似乎增加圆盘数哦！）
不适合处理非常大的问题规模：
- 当问题规模增大时，递归算法的效率会急剧下降，特别是在 n 很大的时候。比如，n = 64 的情况下，递归算法将需要执行 2^64 次操作，几乎无法在合理的时间内完成。
- 对于大规模问题，通常需要使用动态规划或迭代等其他方法来优化。
  
  这是通过服务器运行，20个圆盘的递归运行时间达到了4s！
重复计算：
- 在递归过程中，很多子问题会被重复计算。例如，对于 hanoi(n-1, source, auxiliary, target) 和 hanoi(n-1, auxiliary, target, source)，这些递归会被多次计算，导致冗余计算。虽然汉诺塔本身是一个非常基础的递归问题，但对于更复杂的问题，递归算法可能会带来大量不必要的重复计算。
理解和调试困难（对于初学者）：
- 虽然递归算法在理论上很简单，但在实际调试和执行时，理解递归的执行过程、栈的展开与回收，可能会对初学者造成一定的困扰。特别是对递归的执行顺序和递归返回时的状态恢复需要足够的理解和经验。
- 对于递归的调用栈的管理也比较抽象，调试时可能会比较麻烦。