1. 基础情况：当只有一个圆盘时，直接将它从A移动到C

2. 递归步骤：当有N个圆盘时（N>1）

• 将上面N-1个圆盘从A移动到B（使用C作为辅助）
• 将最大的圆盘从A移动到C
• 将B上的N-1个圆盘移动到C（使用A作为辅助）

def hanoi(n, source, target, auxiliary):
    """
    汉诺塔递归函数
    :param n: 圆盘数量
    :param source: 源柱子
    :param target: 目标柱子
    :param auxiliary: 辅助柱子
    """
    if n == 1:
        # 基础情况：只有一个圆盘时直接移动
        print(f"将圆盘 1 从 {source} 移动到 {target}")
        return
    
    # 将n-1个圆盘从源柱移动到辅助柱
    hanoi(n-1, source, auxiliary, target)
    
    # 移动最底下的圆盘到目标柱
    print(f"将圆盘 {n} 从 {source} 移动到 {target}")
    
    # 将n-1个圆盘从辅助柱移动到目标柱
    hanoi(n-1, auxiliary, target, source)

# 示例：移动3个圆盘，从A柱到C柱，使用B柱作为辅助
hanoi(3, 'A', 'C', 'B')

代码解析：

• 参数说明：n表示圆盘数量，source是起始柱，target是目标柱，auxiliary是辅助柱
• 递归基础：当n=1时，直接移动圆盘并返回
• 递归步骤：将问题分解为三个子任务：移动上层圆盘、移动底层圆盘、再次移动上层圆盘
• 时间复杂度：O(2^n)，因为每一步递归都会产生两个新的递归调用

递归算法要点总结

1. 递归必须有一个或多个基础情况（终止条件）
2. 递归步骤必须逐步趋近基础情况
3. 汉诺塔问题完美展示了"分而治之"的算法思想
4. 递归调用会使用调用栈来保存状态，深度为n时栈深度为n
5. 虽然递归解法简洁，但效率不高，n较大时建议使用非递归算法

汉诺塔移动次数

移动n个圆盘所需的最少移动次数是：2ⁿ - 1

• 1个圆盘：1次移动
• 3个圆盘：7次移动
• 5个圆盘：31次移动
• 8个圆盘：255次移动
• 64个圆盘：18,446,744,073,709,551,615次移动

传说当64个金盘全部移动完成时，世界就会毁灭！