Python 递归导致空列表

Question

我们有一个输入列表，可以有 4 种类型的元素（北、东、南、西）。我们需要删除所有连续的相反方向以简化方向。诀窍在于，通过删除这些方向，我们创建了新的组合，我们也需要检查这些组合。

我已经解决了它，但现在我正在尝试用递归系统来解决它。

这是我的代码：

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 中使用递归。

在列表中使用带有索引

i

的 while 循环，并增加 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"),...}