递归遍历列表（Python）

Question

假设我有一个列表x=[1,2,3,4]

是否存在一种递归方法可以遍历该列表以查找值？

最终，我想能够将列表（或嵌套列表）中的返回值与任意数字进行比较，以查看它是否匹配。

我可以考虑使用for循环来完成此操作，但我难以想象一种递归方法来实现相同的任务。 我知道我不能设置计数器来跟踪列表中的位置，因为每次调用函数时都会重置计数器。

我想将函数的基本情况设置为数字和长度为1的列表之间的比较。

我只是需要一些提示。

- user3272601

---

“num in x” 是什么意思？有什么问题吗？ - squiguy

你也可以将计数器与列表一起传递。 - njzk2

Answer 1

这不是Python中做事情的方式，但是你可以递归遍历一个列表的列表：

def findList(lst, ele):
    if not lst:         # base case: the list is empty
        return False
    elif lst[0] == ele: # check if current element is the one we're looking
        return True
    elif not isinstance(lst[0], list): # if current element is not a list
        return findList(lst[1:], ele)
    else:                              # if current element is a list
        return findList(lst[0], ele) or findList(lst[1:], ele)

- Óscar López

---

它有效 - 可以看到递归通过每次切片列表的“顶部”来工作： 我试图将其应用于嵌套列表，但它不起作用 - 我添加了一个elif语句，如果在列表中找到类型列表的元素，则调用函数处理子列表。但是该函数无法处理更深层的列表。 - user3272601

Answer 2

递归函数在处理链表时是惯用的方法。Python列表更像数组。但仍然可以使用递归函数来处理Python列表--虽然没有真正的实用性，但作为一种练习也是有趣的。

从完整列表开始，当列表为空时为基本情况。通过将列表作为参数传递来遍历列表，使用 x.pop() 同时获取并删除列表中的第一个项目，评估弹出的项目，然后将列表（现在更短）传入同一个函数。

编辑：实际上，经过二次考虑，最好不要使用 x.pop()，而是查看第一个值并将其余部分传递给片段。这样做非常低效，因为每次切片都会复制列表，但比在递归函数内部破坏性地消耗列表更好，除非这是所需的副作用。

- Andrew Gorcester

Answer 3

好的，您将有两个基本情况：

1）您已经到达列表末尾=>返回false。

2）您当前的元素是您要查找的元素=>返回true（或该元素或其位置，取决于您感兴趣的内容）。

您每次必须做的事情是在当前元素上检查这两个基本情况，并在下一个元素上递归应用函数，如果没有一个基本情况适用。

- fedorSmirnov

Answer 4

您可以尝试这个简单的递归解决方案，无需对列表进行切片。

1. 我们检查正在迭代的当前元素是否是 <class 'list'> 的实例，如果是，则需要再次调用该函数（递归）。

2. 否则，我们知道我们已经得到了一些值。因此，在该条件中，我们正在检查搜索元素是否等于该值，如果为真，则找到了搜索元素，否则我们只是简单地打印我们得到的值。

def find_rec(lst, val):
    for ele in lst:
        if isinstance(ele, list): 
            find_rec(ele, val) #recursive function
        else:
            if ele == val:
                print("Found", val)
            else:
                print(ele)

lst = [[1, [10, 20, 30], 100, 200], [999, 120]]
find_rec(lst, 200)

- Ajay S