基于‘舍弃或保留’策略的LCS递归代码崩溃问题排查

核心问题：无限递归的直接原因 #

你的代码完全触发不了基准终止条件——因为你把递归调用use = lcs(...)、result1 = lcs(...)写在了基准判断的前面。程序一进入函数就先递归，根本没机会执行到if s or t == ""这些终止逻辑，直接陷入无限递归导致崩溃。

除此之外，你的基准条件写法也有逻辑错误：

• if s or t == "" 等价于 if (s 非空) or (t == "")，这不是你要的“任意一个字符串为空就返回空”的逻辑，正确写法是if not s or not t（判断字符串是否为空）或者if len(s) == 0 or len(t) == 0。
• 后面的if len(s) or len(t) == 0同样逻辑错误，而且和前面的判断重复，属于冗余代码。

其他逻辑错误 #

1. 拼接逻辑错误：当s[0] == t[0]时，return index_list + s[0] + use完全不合理——index_list是空列表，和字符串拼接会报错，正确的应该是s[0] + use。
2. 非相等情况的错误处理：return result1 or result2只会返回第一个非空的结果，但LCS需要返回更长的那个，如果两个结果长度相同，返回任意一个都可以，但不能直接用or。
3. 冗余变量：index_list和the_string完全没用，属于无效代码。

修正后的完整代码 #

def lcs(s, t):
    """ Arguments are 2 strings s and t. The function outputs a string LCS (longest common subsequence)
    """
    # 基准情况：任意一个字符串为空，直接返回空字符串
    if not s or not t:
        return ""
    
    if s[0] == t[0]:
        # 首字符相等，把该字符加到后续递归的结果前面
        return s[0] + lcs(s[1:], t[1:])
    else:
        # 首字符不等，递归取两种情况中更长的结果
        result1 = lcs(s[1:], t)
        result2 = lcs(s, t[1:])
        return result1 if len(result1) > len(result2) else result2

# 测试用例
assert lcs('mens', 'chimpansee') == 'mns'
assert lcs('gattaca', 'tacgaacta') == 'gaaca'
assert lcs('wow', 'wauw') == 'ww'
assert lcs('', 'wauw') == ''
assert lcs('abcdefgh', 'efghabcd') == 'abcd'

修正说明 #

1. 把基准条件移到函数最开头，确保递归前先判断终止条件，彻底避免无限递归。
2. 修正基准条件的判断逻辑，准确识别空字符串的情况。
3. 调整递归调用的位置：只有当首字符不等时才需要调用两个分支的递归，首字符相等时只需要调用一种递归，减少不必要的计算。
4. 替换or的逻辑，改为比较两个结果的长度，返回更长的LCS。
5. 删除所有冗余无效的变量和代码。

内容的提问来源于stack exchange，提问作者MrPuffer