Python 3: применение рекурсии для сравнения списков?

Question

Я пытаюсь определить функцию со следующим, которая принимает два параметра, list_1 и list_2, и сравнивает их следующим образом: она возвращает False, если list_1 и list_2 имеют разную длину, True, если list_1 и list_2 идентичны, и в противном случаевозвращает индекс первых несовпадающих элементов между списками.

Пока у меня есть это:

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 вызывает «закулисный» цикл 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