递归实现方向化简函数返回空列表问题排查

问题背景 #

我们有一个包含NORTH、EAST、SOUTH、WEST四种元素的输入列表，需要移除所有连续相反方向以简化路径，且移除后产生的新连续相反方向也需处理。已经用非递归方法解决该问题，现在尝试用递归实现，但遇到了逻辑错误。

现有递归代码 #

def dirReduc_recu(arr):

  opposite = {"NORTH" : "SOUTH" , "SOUTH" : "NORTH" , "EAST" : "WEST" , "WEST" : "EAST"}
  i = 1 
  
  if len(arr) <= 1 or all(arr[i] != opposite[arr[i+1]] for i in range(len(arr) - 1)):
    return arr 

  last_element = arr[-1]
  avant_dernier_element = arr[-2]

  if last_element == opposite[avant_dernier_element]:
    arr.pop()
    arr.pop()
    dirReduc_recu(arr)
  else : 
    i += 1 
  return dirReduc_recu(arr[:-i])

测试用例与问题 #

输入测试用例：

["EAST", "EAST", "WEST", "NORTH", "WEST", "EAST", "EAST", "SOUTH", "NORTH", "WEST"]

预期结果为 ['EAST', 'NORTH']，但实际返回空列表。问题出在递归基例的实现逻辑，以及递归过程中对列表的处理方式：

• 基例中尝试判断“无连续相反元素”的写法逻辑上可行，但递归过程中修改原列表后未返回递归结果，且arr[:-i]的处理逻辑混乱，导致最终结果错误。

修正后的递归实现 #

核心思路 #

递归的核心是每次找到第一对连续相反的方向，移除后递归处理新列表；如果遍历完列表都找不到连续相反对，就返回当前列表（这就是正确的基例）。

代码实现 #

def dirReduc_recu(arr):
    opposite = {"NORTH": "SOUTH", "SOUTH": "NORTH", "EAST": "WEST", "WEST": "EAST"}
    
    # 基例1：列表长度小于等于1，无需简化
    if len(arr) <= 1:
        return arr.copy()
    
    # 遍历查找第一对连续相反的方向
    for i in range(len(arr) - 1):
        if arr[i+1] == opposite[arr[i]]:
            # 移除这对元素，生成新列表后递归处理
            new_arr = arr[:i] + arr[i+2:]
            return dirReduc_recu(new_arr)
    
    # 基例2：没有找到任何连续相反对，返回当前列表
    return arr.copy()

代码说明 #

1. 基例明确：要么列表长度≤1，要么遍历后无连续相反元素，直接返回列表副本（避免外部修改影响递归结果）。
2. 递归逻辑清晰：每次找到第一对相反元素就移除，递归处理新列表，确保每次递归都处理最新的列表状态。
3. 避免修改原列表：用切片生成新列表，不会影响递归过程中的其他分支状态。

测试验证 #

运行测试用例：

test_case = ["EAST", "EAST", "WEST", "NORTH", "WEST", "EAST", "EAST", "SOUTH", "NORTH", "WEST"]
print(dirReduc_recu(test_case))  # 输出 ['EAST', 'NORTH']，符合预期

内容的提问来源于stack exchange，提问作者Léandre Rq