Python递归导致空列表

Question

我们有一个输入列表，这个列表里可能有四种方向的元素（北、东、南、西）。我们的目标是去掉所有相邻的相反方向，以简化方向。这里的关键在于，去掉这些方向后，会产生新的组合，我们也需要检查这些组合。

我已经解决了这个问题，但现在我想用递归的方法来实现。

这是我的代码：

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']

但是我得到的是一个空列表。

我觉得问题出在我的基本情况设置上。在我看来，基本情况应该是“遍历列表。如果你从未找到任何相反的元素，就返回这个列表。”我不知道怎么把这个想法转化成Python代码。

Answer 1

我在Python中不会用递归来解决这个问题。

可以用一个while循环，里面用一个索引i来遍历列表，然后要么增加i的值，要么删除两个元素。

def dirReduc(a):
    i = 0
    while i < ...:
        if tuple(a[i:i+2]) in dirReduc.opposites:
            ...
        else:
            ...
    return a
dirReduc.opposites = {("NORTH","SOUTH"),("SOUTH","NORTH"),...}

Answer 2

在你的尝试中有几个问题：

• 第一次递归调用修改了 arr，但是它返回的列表被忽略了。

• 第二次递归调用传递了一个新的列表，这个列表的值少了一些（少一两个），而且这个列表也是它返回的（可能已经被修改过）。这意味着列表末尾的一些值丢失了，而这没有什么好的理由。

这里有一种可能的递归应用方法：

opposite = {"NORTH" : "SOUTH" , "SOUTH" : "NORTH" , "EAST" : "WEST" , "WEST" : "EAST"}
  
def dirReduc_recu(lst):
    if len(lst) < 2:
        return lst
    rest = dirReduc_recu(lst[1:])
    return rest[1:] if rest and lst[0] == opposite[rest[0]] else lst[:1] + rest

在这里，列表没有被修改；返回的是新的列表，只有在基本情况时才会返回原来的列表。

对于更大的列表，这样会占用过多的内存；更好的方法是对给定列表的一半进行递归，然后通过消除接触的部分来合并这两半：

opposite = {"NORTH" : "SOUTH" , "SOUTH" : "NORTH" , "EAST" : "WEST" , "WEST" : "EAST"}
  
def dirReduc_recu(lst):
    if len(lst) < 2:
        return lst
    # partition
    mid = len(lst) // 2
    left = dirReduc_recu(lst[:mid])
    right = dirReduc_recu(lst[mid:])
    # merge
    for i, (a, b) in enumerate(zip(reversed(left), right)):
        if a != opposite[b]:
            return left[:-i] + right[i:] if i else left + right
    i = min(len(left), len(right))
    return left[:-i] + right[i:]