Python汉诺塔递归代码疑问：n=1时参数为何是A、B、C而非A、C、B？

问题代码 #

def move_disks(n, from_tower, to_tower, aux_tower):
    result = []
    # base case
    if n == 1:
        return [f"Move disk {n:} from {from_tower:} to {to_tower:}."]
    # recursive case
    else:
        # move n-1 disks from src to an aux tower
        result = move_disks(n-1, from_tower, aux_tower, to_tower)
        # move nth disk src to dest tower
        result += [f"Move disk {n:} from {from_tower:} to {to_tower:}."]
        # move n-1 disks from aux to dest
        result += move_disks(n-1, aux_tower, to_tower, from_tower)
    
    return result

# Test cases
result = move_disks(3, "A", "B", "C")
print(result)
assert result == ["Move disk 1 from A to B.", "Move disk 2 from A to C.", "Move disk 1 from B to C.", "Move disk 3 from A to B.", "Move disk 1 from C to A.", "Move disk 2 from C to B.", "Move disk 1 from A to B."]

疑问与解答 #

你观察到调用move_disks(3, "A", "B", "C")递归到n=1时，参数为(A, B, C)，疑惑为什么不是(A, C, B)，这是因为递归调用的参数是根据当前步骤的移动目标动态调整的，逻辑如下：

• 顶层目标：把3个盘子从A移到B，辅助塔是C。
• 第一步递归：要完成顶层目标，首先得把上面2个盘子从A移到C（临时存放），所以调用move_disks(2, "A", "C", "B")——这里的目标塔变成了C，辅助塔变成了B。
• 第二层递归（n=1的调用）：在处理move_disks(2, "A", "C", "B")时，第一步需要把最上面的1个盘子从A移到B（临时存放，这样才能把第2个盘子从A移到C），所以调用move_disks(1, "A", "B", "C")，这就是你看到的n=1时的参数组合。

这个参数是完全正确的，对应测试用例输出的第一条结果Move disk 1 from A to B.，正是这一步调用的返回值，完全符合汉诺塔的移动逻辑：先把小盘子移到临时塔，才能移动下面的大盘子。

内容的提问来源于stack exchange，提问作者Yash Mehta