Максимальная Рекурсия в ЛВПЕ рекурсивной функции

Question

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

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

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

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

Answer 2

Я не совсем понимаю вашу логику: на каждой итерации вы либо перемещаете первый символ в конец строки, либо бросаете его и добавляете #. только Этап сокращения в этом сокращает 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.

Answer 3

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

И пристальный взгляд, это не имеет смысла:

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.