python - 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 中添加了一个元素，所以传递的字符串的大小与电话。