hanoi塔问题的递归算法

Hanoi塔问题是一个经典的递归问题，也称为汉诺塔游戏。它涉及三个柱子A、B和C以及一堆大小为n的圆盘，规则是每次只能移动一个圆盘，并且始终要保证大盘子在小盘子之上。以下是解决Hanoi塔问题的递归算法步骤：

1. **基本情况**：当只有一个圆盘（n=1）时，直接从A柱移到C柱，因为此时不需要其他柱子。

2. **递归调用**：假设我们有n-1个圆盘，可以将它们从A柱通过B柱移动到C柱，这是递归的过程。这时，A柱上只剩下一个大圆盘。

3. **解决当前圆盘**：将剩余的一个圆盘从A柱直接移动到C柱。

4. **完成递归**：最后，将之前放在B柱上的n-1个圆盘按照同样的递归策略从B柱通过A柱移到C柱。

递归算法的伪代码如下：

def hanoi(n, source, auxiliary, target):
    if n > 0:
        # 递归地将前n-1个圆盘移动到辅助柱子
        hanoi(n - 1, source, target, auxiliary)
        
        # 将最大的圆盘移动到目标柱子
        print(f"Move disk {n} from {source} to {target}")
        
        # 最后，把辅助柱子剩下的n-1个圆盘移回目标柱子
        hanoi(n - 1, auxiliary, source, target)

# 调用函数，比如hanoi(3, 'A', 'B', 'C')