Python 3 : applying recursion to compare lists?

Question

我试图定义一个函数，它接受两个参数，list_1 和 list_2，并按如下方式比较它们:如果 list_1 和 list_2 具有不同的长度，则返回 False；如果 list_1 和 list_2 相同，则返回 True；否则返回列表之间第一个不匹配元素的索引。

到目前为止我有这个:

if len(list_1) != len(list_2):
    return False
elif list_1 == list_2:
    return True
else:
    i = 0
    if list_1[i] == list_2[i]:
        return i
    else:
        i += 1
        compare_lists(list_1, list_2)

从逻辑上讲，当我再次调用该函数时，我会不断重置为 0。有谁知道我该如何克服这个问题？

Answer 1

您必须将i工作变量传递给每个函数。

此外，您不应该检查每个函数中的列表是否相等或者它们的长度是否不同，因为这会破坏递归的意义，因为 list_1 == list_2 语句会导致“behind -the-scenes” for 循环迭代两个列表。这会大大降低性能。

相反，只需捕获当前索引超出其中一个列表末尾的情况即可。在这种情况下，如果它们的长度相同，那么我们可以返回True；否则我们返回False，因为我们已经到达了一个的末尾，但还没有到达另一个。

如果上述情况不适用于此函数调用的索引，我们只需检查索引处的元素是否相同。如果不是，我们返回索引(该索引将通过我们的父级传递给初始调用者)。否则，我们返回使用相同列表调用自己(子级)的结果，但索引递增(i + 1)。

def compare_lists(list_1, list_2, i=0):
    l1 = len(list_1)
    l2 = len(list_2)
    if i >= l1 or i >= l2:
        return l1 == l2
    if list_1[i] != list_2[i]:
        return i
    return compare_lists(list_1, list_2, i+1)

按预期工作:

>>> compare_lists([6,4,2], [6,4,2])
True
>>> compare_lists([6,4,2], [6,4,3])
2
>>> compare_lists([6,4,2], [6,4])
False