Skip to main content
 首页 » 编程设计

python之LCS 递归函数中的最大递归

2025年04月02日9java哥

我正在尝试执行一个 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 中添加了一个元素,所以传递的字符串的大小与电话。