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))TrueFalse上面我们写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))TrueFalse

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验证当前级别中的所有项目后将执行附加操作如果完成所有项目但未找到 - 完成当该项目有更多机会出现在外部列表中时效果更好