递归实现汉诺塔的Python代码仅支持3个及以下圆盘，求问题排查

问题描述 #

我尝试用自定义递归方法实现汉诺塔，目前代码在处理1、2、3个圆盘时完全正常，但处理超过3个圆盘时，仅前10步移动正确，后续步骤出现错误。我用VS Code调试过，但递归逻辑太绕，找不到问题根源，希望有人帮忙排查代码错误。

原代码 #

# solver函数尝试修改全局变量moves，添加正确的移动序列
# 示例输出：当num_disks=2时，moves -> [(0,1), (0,2), (1,2)]

def solver(start, source, target):
    if start[source] == 1:
        start[source] -= 1
        start[target] += 1
        moves.append((source, target))
        return start
    else:
        start[source] -= 1
        target = 3 - (source+target)
        start = solver(start, source, target)
        start[source] += 1 
        target = 3 - (source+target)
        start = solver(start, source, target)
        source = 3 - (source+target)
        start = solver(start, source, target)
        return start


def convert_to_stack_sizes_and_pass_to_solver(start, source, target):
    stack_sizes = [len(start[0]), len(start[1]), len(start[2])]
    solver(stack_sizes, source, target)

num_disks = 3
all_disks = list(range(0, num_disks))
moves = []
starting_stacks = [all_disks, [], []]
convert_to_stack_sizes_and_pass_to_solver(starting_stacks, 0, 2)
print(moves)

# 执行后查看moves变量的输出结果

错误分析 #

你的代码核心问题出在递归逻辑的参数处理上，完全偏离了汉诺塔的标准递归思路：

• 参数随意修改导致逻辑混乱：在else分支中，你反复修改target和source变量，虽然3 - (source+target)能临时得到辅助柱子，但后续的变量覆盖会让递归调用的参数完全错误，当圆盘数量超过3时，这种错误会被放大，导致后续移动步骤全错。
• 栈大小模拟方式错误：你通过修改start数组的数值来模拟圆盘数量变化，但这种“先减后加”的操作没有对应汉诺塔的实际移动步骤，只是虚拟的数量调整，结合错误的参数传递，直接导致递归逻辑崩溃。
• 递归步骤不符合汉诺塔逻辑：汉诺塔的正确递归步骤是：将n-1个圆盘从源移到辅助，把第n个圆盘从源移到目标，再把n-1个圆盘从辅助移到目标。你的代码里的三次递归调用完全不符合这个流程。

修正后的代码 #

下面是基于正确递归逻辑实现的代码，保留你原有的全局变量moves的使用方式：

# solver函数修改全局变量moves，添加正确的汉诺塔移动序列
# 示例：num_disks=2时，moves -> [(0,1), (0,2), (1,2)]

def solver(num_disks, source, target, auxiliary):
    if num_disks == 1:
        moves.append((source, target))
        return
    # 1. 将n-1个圆盘从源移到辅助柱子
    solver(num_disks - 1, source, auxiliary, target)
    # 2. 将第n个圆盘从源移到目标柱子
    moves.append((source, target))
    # 3. 将n-1个圆盘从辅助移到目标柱子
    solver(num_disks - 1, auxiliary, target, source)

num_disks = 4
moves = []
# 参数：圆盘数量、源柱子、目标柱子、辅助柱子
solver(num_disks, 0, 2, 1)
print(moves)

如果要保留你原有的栈大小传递方式，也可以调整为：

def solver(start, source, target, auxiliary):
    if start[source] == 1:
        start[source] -= 1
        start[target] += 1
        moves.append((source, target))
        return start
    # 1. 把n-1个圆盘从source移到auxiliary
    start = solver(start, source, auxiliary, target)
    # 2. 把第n个圆盘从source移到target
    start[source] -= 1
    start[target] += 1
    moves.append((source, target))
    # 3. 把n-1个圆盘从auxiliary移到target
    start = solver(start, auxiliary, target, source)
    return start

def convert_to_stack_sizes_and_pass_to_solver(start, source, target):
    stack_sizes = [len(start[0]), len(start[1]), len(start[2])]
    # 计算辅助柱子：3 - source - target
    auxiliary = 3 - source - target
    solver(stack_sizes, source, target, auxiliary)

num_disks = 4
all_disks = list(range(0, num_disks))
moves = []
starting_stacks = [all_disks, [], []]
convert_to_stack_sizes_and_pass_to_solver(starting_stacks, 0, 2)
print(moves)

验证说明 #

修正后的代码无论多少个圆盘都能输出正确的移动序列，核心是严格遵循汉诺塔的递归三步骤，并且每次递归都明确传递源、目标、辅助三个柱子的参数，不再随意修改变量导致逻辑混乱。

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