Python递归求解坐标移动问题无法终止，求代码修复及优化方案

递归无法终止的核心原因 #

• 递归返回逻辑不完整：if分支里的return仅会终止当前层级的函数调用，当前调用层剩余的3个后续elit()递归调用依然会执行，并不会终止整个递归链
• timer是值传递的局部变量：Python中整数属于不可变类型，函数内对timer的修改不会同步到其他递归分支，timer == ways的判断条件几乎不可能触发，自然无法靠这个条件停止全部递归
• 无边界兜底终止逻辑：即使满足终止条件的分支return了，其他没有触发终止条件的递归分支依然会向下执行，直到栈溢出

现有代码的其他逻辑错误 #

• 终点匹配逻辑完全错误：你将终点坐标存为了无序集合end_set = {int(x_end), int(y_end)}，但路径终点存的是有序元组(x,y)，集合和元组类型不一致，永远不可能匹配成功
• 递归复杂度不可用：4的n次方的时间复杂度，只要count>10就会出现严重的性能问题，count>20基本不可能跑出结果

最优实现方案 #

这个问题不需要递归遍历所有路径，直接通过数学规则判断即可：

1. 先计算起点到终点的曼哈顿距离：d = abs(x_start - x_end) + abs(y_start - y_end)
2. 同时满足两个条件就存在合法路径：
   • 总移动次数count >= d：最少需要d步才能走到终点
   • count - d是偶数：多出来的步数可以走“前进1步+后退1步”的组合抵消，刚好凑够总步数
3. 符合条件输出Y，否则输出N

优化后代码 #

# 输入处理
x_start, y_start = map(int, input().split())
x_end, y_end = map(int, input().split())
count = int(input())

# 计算曼哈顿距离
manhattan = abs(x_start - x_end) + abs(y_start - y_end)

# 逻辑判断
if count >= manhattan and (count - manhattan) % 2 == 0:
    print("Y")
else:
    print("N")

样例验证 #

样例输入起点(3,4)、终点(3,3)、移动次数3：曼哈顿距离为1，3≥1且3-1=2为偶数，输出Y，符合要求。

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