我正在尝试执行一个 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)
请您参考如下方法:
在您的第一个递归调用中 (count = 1 + LCS(s1[1:], s2[1:])),因为您刚刚在每个 的末尾添加了一个元素>s1 和 s2,传递的字符串大小与调用中的相同,因此您在终止方面没有任何进展
在 max 中,第二次递归调用有同样的问题:你在 s1 中添加了一个元素,所以传递的字符串的大小与电话。
