Python 函数递归 - 给出"列表"中第一次出现的"数字"的索引，如果数字不在列表中，则返回 None。

Question

我有一个练习，我需要找到一个数字在列表中的第一个出现的索引。但我也需要返回None，如果索引不能找到，这意味着数字不在列表中。我需要用Python中的递归函数来完成。

我已经创建了一个代码来"查找列表中第一个出现的数字的索引"。

def index(lst, number_find):
if lst == []:
return None
elif lst[0] == number_find:
return 0
else:
return 1 + index(lst[1:], number_find)
liste = range(51)
print(index(liste, 42))

但是如果数字不在列表中，我就不能编写管理这种情况的代码。我已经做到了:

def index(lst, number_find):
if number_find not in lst: 
return None
elif lst == []:
return None
elif lst[0] == number_find:
return 0
else:
return 1 + index(lst[1:], number_find)
liste = range(51)
print(index(liste, 42))

但是"not in"对我来说不是很好，因为它似乎使用了一些我不会使用的迭代代码。

Answer 1

您必须防止None从递归调用返回的情况，因为1 + None将引发TypeError:

def index(lst, number_find):
if lst == []:
return None
elif lst[0] == number_find:
return 0
else:
i = index(lst[1:], number_find)
if i is not None:
return 1 + i
return None  # not strictly necessary as None returned implicity

当然，当您从每个if块返回时，您可以省略任何else。另外，None是默认返回值，因此您可以缩短逻辑

def index(lst, number_find):
if lst:
if lst[0] == number_find:
return 0
if (i := index(lst[1:], number_find)) is not None:
return 1 + i

Btw，由于切片在这里是O(N)，所有这些方法都是二次的。这里有一个线性复杂度的解决方案:

def index(lst, number_find):
def rec(it, i=0):
if (n := next(it, None)) is not None:
return i if n == number_find else rec(it, i+1)
return rec(iter(lst))

Answer 2

user2390182接受的答案详细说明了如何处理递归调用返回的可能的None值。

另一种方法是以尾部递归的方式编写函数:

def index(lst, number_find, acc=0):
if lst == []:
return None
elif lst[0] == number_find:
return acc
else:
return index(lst[1:], number_find, acc+1)

请注意python不执行尾部搜索优化;但这种方法仍然避免了1+None问题。