python - 用于查找值索引的递归和返回

Question

因此，我在一张 CSE 101 幻灯片中遇到了一个练习题，该问题要求使用递归在列表或字符串中查找值。如果该值位于列表或字符串内，则返回与该值匹配的第一个索引位置。我能够解决它，但我不明白它为什么有效。这是我的代码:

def rindex(a, pos):
    if pos not in a:
        return None
    elif pos in a:
        if a[0] != pos:
            return rindex(a[1:], pos) + 1
    return 0

具体来说，我不明白为什么

return 0

使我的功能正常工作。为什么它返回正确的值而不是 0？

Answer 1

每次在函数中遇到 return 时，都会返回结果并停止函数执行。这意味着，如果 pos 存在于当前 a 切片中，则永远不会遇到 return 0，除非当前切片的第一个元素等于 pos - 此时您返回 0 以指示索引不应增加。如果您不返回它，则默认情况下，rindex() 将返回 None，当您尝试将其与 + 1 求和时，会导致错误递归链。

话虽这么说，每当你执行 if pos not in a: 时，你都会迭代列表 a 来搜索 pos 所以您的代码将非常低效(特别是因为您随后在 elif block 中再次执行完全相同的搜索，而简单的 else 就足够了)。您可以将代码重新编写为:

def rindex(a, pos):
    if a[0] == pos:  # element found, do not increase the index
        return 0
    return rindex(a[1:], pos) + 1

因此，每次递归时您只进行切片而不是两次迭代。这里最大的问题是，如果在列表递归到达末尾时未找到 pos，它将引发 IndexError。如果您更喜欢返回值而不是异常，您可以捕获它并返回任何类型的值，因此在您的情况下:

def rindex(a, pos):
    if a[0] == pos:  # element found, do not increase the index
        return 0
    try:
        return rindex(a[1:], pos) + 1
    except (IndexError, TypeError):  # capture both to propagate
        return None

但是，请记住，即使执行列表切片也不是最有效的解决方案，尤其是在考虑内存时。由于 Python 将名称传递给引用，因此您可以递归整个列表，而几乎没有任何损失，并使用索引递归地遍历列表，即:

def rindex(a, pos, loc=0):
    if a[loc] == pos:
        return loc
    return rindex(a, pos, loc+1)

您甚至不必执行递归try .. except编排来捕获错误 - 您可以直接在函数中执行抢占式( LBYL 样式):

def rindex(a, pos, loc=0):
    if len(a) >= loc:
        return None
    if a[loc] == pos:
        return loc
    return rindex(a, pos, loc + 1)

或者事后(EAFP风格):

def rindex(a, pos, loc=0):
    try:
        if a[loc] == pos:
            return loc
    except IndexError:
        return None
    return rindex(a, pos, loc + 1)

当未找到元素时，这些还允许您传递任意索引(即 -1)，因为验证与实际索引搜索分开，因此不会影响索引总和。