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

在您的第一个递归调用(count = 1 + LCS(s1[1:], s2[1:]))中，由于您只是在s1和s2的末尾添加了一个元素，因此传递的字符串的大小与调用中的字符串的大小相同，因此您并没有朝着终止的方向前进

在max内部，第二个递归调用具有相同的问题:您向s1添加了一个元素，因此传递的字符串的大小与调用中的相同。

Answer 2

正如其他人所说的，您正在向string变量添加一个字符，并在下一次递归调用中去掉一个字符。这样，总是会有具有初始长度的字符串的递归调用，从而导致无限递归。

仔细一看，这是不合理的：

    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 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之间来回切换。