在LCS遞歸函數

我試圖來執行遞歸利用給我的位置數的LCS是有效的，與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)

來源

2016-09-19 priya

在你的第一個遞歸調用（count = 1 + LCS(s1[1:], s2[1:])），因爲你剛剛添加的元素到每個s1和s2末，傳遞字符串的大小是相同的電話，所以你在做沒有任何進展終止

在max的內部，第二次遞歸調用具有相同的問題：您向s1添加了一個元素，所以傳遞的字符串的大小與調用中的大小相同。

來源

2016-09-19 18:05:33

我完全不清楚自己的邏輯：在每次迭代中，您要麼將第一個字符移動到字符串末尾，要麼將其刪除並追加一個＃。只有這個縮小步驟縮短了較低分支中的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之間永久彈起。

來源

2016-09-19 18:09:53 Prune

正如其他人所說的，您正在爲字符串變量添加一個字符，並在下一次遞歸調用中關閉一個字符。這樣，總是會有一個具有初始長度的字符串的遞歸調用，從而導致無限遞歸。

而且隨着仔細一看，這是沒有意義的：

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運行。

來源

2016-09-19 18:35:24 trincot

在LCS遞歸函數

回答

相關問題