Максимальная рекурсия в рекурсивной функции LCS

Question

Я пытаюсь выполнить функцию LCS, которая использует рекурсию, чтобы дать мне количество позиций, которые действительны LCS, наряду с местом LCS, изображенным здесь:

input: LCS("smile", "tile")
output: [3, "##ile", "#ile"]

Всякий раз, когда я пытаюсь выполнить его, он говорит мне, что есть ошибка рекурсии, как показано ниже:

RecursionError: maximum recursion depth exceeded in comparison

Что не так с моим кодом? Я попытался заменить области, где LCS не применялся через рекурсию, но где функция превышает ее глубину?

def LCS(s1, s2):
    if s1 == "" or s2 == "":
        return 0
    else:
        if s1[0] == s2[0]:
            s1 = s1 + s1[0]
            s2 = s2 + s2[0]
            count = 1 + LCS(s1[1:], s2[1:])
        else: 
            s1 = s1 + '#'
            count = max(LCS(s1, s2[1:]), LCS(s1[1:], s2))
    array = [count] + [s1] + [s2]
    print(array)

Answer 1

Как утверждают другие, вы добавляете символ в строковую переменную и отбираете его в следующем рекурсивном вызове. Таким образом, всегда будут рекурсивные вызовы со строкой, которая имеет начальную длину, что приводит к бесконечной рекурсии.

И при ближайшем рассмотрении это не имеет смысла:

    if s1[0] == s2[0]:
        s1 = s1 + s1[0]

Здесь вы снова добавляете первый символ в конец строки. Это не может быть правдой.

Также функция имеет возможность вернуть только 0 (или None), но не более того. Это также не может быть правдой. Что бы ни делала функция, она всегда должна возвращать значение.

Поскольку вы заинтересованы в подсчете совпадающих символов и # заполненные версии обеих исходных строк, вы можете позволить вашей функции возвращать три значения (список) вместо одного.

Затем код можно заставить работать так:

def LCS(s1, s2):
    if s1 == "" or s2 == "":
        return 0, '#' * len(s1), '#' * len(s2)
    else:
        if s1[0] == s2[0]:
            count, r1, r2 = LCS(s1[1:], s2[1:])
            return  count+1, s1[0] + r1, s2[0] + r2
        else:
            count1, r11, r12 = LCS(s1, s2[1:])
            count2, r21, r22 = LCS(s1[1:], s2)
            if count2 > count1:
                return count2, '#' + r21, r22
            else:
                return count1, r11, '#' + r12

print (LCS ('smile', 'tile'))

Выход:

(3, '##ile', '#ile')

Смотрите это запустить на repl.it.

Answer 2

В вашем первом рекурсивном вызове (count = 1 + LCS(s1[1:], s2[1:])), так как вы только что добавили элемент в конец каждого из s1 а также s2размеры передаваемых строк такие же, как в вызове, поэтому вы не продвигаетесь к завершению

Внутри maxВторой рекурсивный вызов имеет ту же проблему: вы добавили элемент s1Таким образом, размеры передаваемой строки такие же, как в вызове.

Answer 3

Я не совсем понимаю вашу логику: на каждой итерации вы либо перемещаете первый символ в конец строки, либо отбрасываете его и добавляете знак #. Единственный шаг сокращения в этом - сокращение s2 в нижней ветви, но вы попадете в бесконечную рекурсию, прежде чем доберетесь туда. Я добавил простую трассировку в начало процедуры:

def LCS(s1, s2):
    print("ENTER s1=", s1, "\ts2=", s2)

Вот как это застревает:

ENTER s1= smile     s2= tile
ENTER s1= smile#    s2= ile
ENTER s1= smile##   s2= le
ENTER s1= smile###  s2= e
ENTER s1= smile####     s2= 
ENTER s1= mile####  s2= e
ENTER s1= mile#####     s2= 
ENTER s1= ile#####  s2= e
ENTER s1= ile######     s2= 
ENTER s1= le######  s2= e
ENTER s1= le#######     s2= 
ENTER s1= e#######  s2= e
ENTER s1= #######e  s2= e
ENTER s1= #######e#     s2= 
ENTER s1= ######e#  s2= e
ENTER s1= ######e##     s2= 
ENTER s1= #####e##  s2= e
ENTER s1= #####e###     s2= 
ENTER s1= ####e###  s2= e
ENTER s1= ####e####     s2= 
ENTER s1= ###e####  s2= e
ENTER s1= ###e#####     s2= 
ENTER s1= ##e#####  s2= e
ENTER s1= ##e######     s2= 
ENTER s1= #e######  s2= e
ENTER s1= #e#######     s2= 
ENTER s1= e#######  s2= e
ENTER s1= #######e  s2= e

---

Когда вы терпите неудачу в прогоне, вам нужно сбросить s2 к его первоначальному значению. Ваш текущий код резервируется с еще одним символом в каждой строке, оставляя s2 постоянно подпрыгивая между его последним символом и NULL.