Python 递归与嵌套列表

Question

我正在尝试创建一个递归函数，该函数遍历具有单个字符串的任何级别的嵌套列表，并返回 True 或 False 无论给定字符是否在该列表中。这是我的代码：def inlist(character, lists):    """Checks if a given character is in a list of any level"""        if lists[0] == character:        return True        elif isinstance(lists[0], list):        return inlist(character,lists[0])        elif not lists[0] == character:        return inlist(character,lists[1:])        else:        return False当我运行代码时： ("c", [["a", "b","c", "d"],"e"])它似乎工作正常。但是，当我以这种方式输入列表时： ("c", [["a", "b",],["c", "d"],"e"])它给了我一个错误，它说：IndexError：列表索引超出范围我可以不这样写嵌套列表吗？如果是这样，为什么？或者我的代码有什么问题导致它无法遍历整个列表？

Answer 1

采用纯递归方法，就像问题中使用的那样：

def inlist(char, lists):

    if not lists: # check for empty list

        return False

        

    if lists[0] == char:

        return True

    elif isinstance(lists[0], list) and inlist(char, lists[0]):

        return True # return only if found in sublist, otherwise continue

    elif len(lists) > 1: # check rest of the list, if there is a rest

        return inlist(char, lists[1:])

        

    return False # all possibilities exhausted. Char not in this (sub-)list

这对于某些问题可能很有用，但要在列表中查找元素，循环会更快。此外，对于较长的列表，最大递归深度将是一个问题。

Answer 2

在这种isinstance(lists[0], list)情况下，您仍然必须小心检查lists[1]递归调用是否返回 false。

在获取值之前始终检查列表是否为空。这是使用高阶函数（例如 ）来思考问题的另一种方法some。

def some(f, t):

  if not t:

    return False

  else:

    return f(t[0]) or some(f, t[1:])

def inlist(char, ls):

  return some \

    ( lambda v: inlist(char, v) if isinstance(v, list) else char == v

    , ls

    )

input = ["c", [["a", "b",],["c", "d"],"e"]]

print(inlist("a", input))

print(inlist("z", input))

True

False

上面我们写some的作为练习。你应该知道 Python 有一个内置any函数 -

def inlist(char, ls):

  return any(isinstance(v, list) and inlist(char, v) or char == v for v in ls)

input = ["c", [["a", "b",],["c", "d"],"e"]]

print(inlist("a", input))

print(inlist("z", input))

True

False

Answer 3

你把它弄得有点复杂，而递归时的思维方式应该简单得多

DFS-ish 版本：

（你可以在网上阅读更多关于DFS遍历的内容）

def inlist(character, lists):

    """Checks if a given character is in a list of any level"""

    for item in lists:

        if item==character:

            return True

        if isinstance(item, list):

            if inlist(character, item):

                return True

    return False

    

            

        

a = ["c", [["a", "b",],["c", "d"],"e"]]

print(inlist("a", a))

输出：

True

对于此输入：

print(inlist("z", a))

输出是：

False

简短说明：

循环遍历列表中的所有项目

如果该项目是角色 - 完成

如果该项目是列表 - 立即调用递归（这里吸引人的部分是仅在 True 时返回，因为如果不是 - 这并不意味着在其他项目中找不到该字符）

如果完成所有项目但未找到 - 完成

当该项目有更多机会出现在内部列表中时效果更好

BFS 版本：

（你可以在网上阅读更多关于BFS遍历的内容）

def inlist(character, lists):

    """Checks if a given character is in a list of any level"""

    extra_arr = []

    for item in lists:

        if item==character:

            return True

        if isinstance(item, list):

            extra_arr.append(item)

    

    for extra_item in extra_arr:

        if inlist(character, extra_item):

            return True

    return False

当然，结果是一样的。

简短说明：

循环遍历列表中的所有项目

如果该项目是角色 - 完成

如果该项目是列表 -extra_arr验证当前级别中的所有项目后将执行附加操作

如果完成所有项目但未找到 - 完成

当该项目有更多机会出现在外部列表中时效果更好