3

我正在尝试执行一个 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)
4

3 回答 3

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上运行。

于 2016-09-19T18:35:24.973 回答
1

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

在 内部max，第二个递归调用有同样的问题：你添加了一个元素到s1，所以被传递的字符串的大小与调用中的相同。

于 2016-09-19T18:05:33.753 回答
0

我完全不清楚您的逻辑：在每次迭代中，您要么将第一个字符移动到字符串的末尾，要么将其删除并附加一个#。唯一的减少步骤是在较低的分支中缩短 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-19T18:09:53.853 回答