Python 轻松解决汉诺塔问题：从递归到迭代算法详解147

汉诺塔（Tower of Hanoi）是一个经典的数学游戏，也是计算机科学中递归算法的典型例题。它由三个杆子和一系列大小不一的圆盘组成。起初，所有圆盘都按大小顺序叠放在一个杆子上，最大的圆盘在底部。目标是将所有圆盘移动到另一个杆子上，每次只能移动一个圆盘，并且任何时候都不能将较大的圆盘放在较小的圆盘上面。这篇文章将深入探讨如何用Python编程解决汉诺塔问题，从最直观的递归解法到更高效的迭代解法，并分析其时间复杂度和空间复杂度。

一、递归算法：优雅而简洁的解决方案

汉诺塔问题的递归解法非常简洁，它符合问题的自然逻辑：将n个圆盘从源柱移到目标柱，可以分解为以下三个步骤：
将n-1个较小的圆盘从源柱移动到辅助柱。
将最大的圆盘（第n个圆盘）从源柱移动到目标柱。
将n-1个较小的圆盘从辅助柱移动到目标柱。

Python代码实现如下：```python
def hanoi(n, src, dst, aux):
"""
递归解法实现汉诺塔问题。
Args:
n: 圆盘数量。
src: 源柱编号。
dst: 目标柱编号。
aux: 辅助柱编号。
"""
if n == 1:
print(f"Move disk 1 from {src} to {dst}")
else:
hanoi(n - 1, src, aux, dst)
print(f"Move disk {n} from {src} to {dst}")
hanoi(n - 1, aux, dst, src)
# 测试：移动3个圆盘
hanoi(3, 'A', 'C', 'B')
```

这段代码清晰地展现了递归的思想。当只有1个圆盘时，直接移动即可；否则，递归调用自身来解决子问题。递归算法的优雅之处在于其代码简洁，易于理解，它直接反映了问题的解题思路。然而，其缺点也很明显：对于较大的n值，递归深度会非常大，容易造成栈溢出错误。

二、迭代算法：克服递归的局限性

为了避免递归带来的栈溢出问题，我们可以使用迭代算法来解决汉诺塔问题。迭代算法的核心思想是模拟递归过程，使用循环和栈结构来替代递归调用。以下是一个基于栈的迭代算法：```python
def hanoi_iterative(n, src, dst, aux):
"""
迭代解法实现汉诺塔问题。
Args:
n: 圆盘数量。
src: 源柱编号。
dst: 目标柱编号。
aux: 辅助柱编号。
"""
stack = [(n, src, dst, aux)]
while stack:
num, src, dst, aux = ()
if num == 1:
print(f"Move disk 1 from {src} to {dst}")
else:
((num - 1, aux, dst, src))
((1, src, dst, aux))
((num - 1, src, aux, dst))
# 测试：移动3个圆盘
hanoi_iterative(3, 'A', 'C', 'B')
```