python - 即使基本情况是完美的，递归也不会终止

Question

我一直在尝试 this问题。我的想法是尝试所有可能的组合，如果可行，那么我将继续进行内存。但实际上递归并没有停止。这是我的算法。

这是我写的代码:

def min_edits(s1, s2):
    if len(s1) == 0 and len(s2) == 0:
        return 0
    elif len(s1) == 0 or len(s2) == 0:
        return float("inf")
    elif s1[0] == s2[0]:
        return 1 + min_edits(s1[1:], s2[1:])
    else:
        replace = min_edits(s2[0] + s1[1:], s2)  # Replace the first character of first string with that of second one
        insert = min_edits(s2[0] + s1, s2)  # Adds the first character of second string to first one
        delete = min_edits(s2[1:], s2)  # delete first character of first string
        return min(
            insert,
            replace,
            delete
        )


if __name__ == '__main__':
    tc = int(input())
    for i_tc in range(tc):
        input()
        (s1, s2) = input().split(" ")
        answer = min_edits(s1, s2)
        print(answer)

这是递归树:

在该递归树中，第一个分支是替换，第二个分支是插入，最后一个分支是删除

“_”表示只有一个字符串为空，函数返回无穷大。

所以我们可以清楚地看到树在所有情况下都会终止。

但它仍然说超出了最大递归深度。

请告诉我哪里做错了。谢谢:)

Answer 1

问题是参数的长度并没有在每一步都减少，这对于递归调用达到基本情况至关重要。在替换中，两个字符串的长度保持不变，而在插入步骤中，一个字符串的长度实际上增加了。

那么，我们所说的替换、删除或插入是什么意思？例如，假设我们有字符串:

ABCD and DECD

然后，如果我们正在查看索引 0，则替换/删除调用将为我们留下 BCD 和 ECD，而插入将为我们留下 ABCD 和 ECD，或 BCD 和 DECD。使用这种方法，至少一个字符串的长度总是会减少，因此我们可以保证达到基本情况。

编辑:正在达到基本情况，但逻辑存在问题，因此我添加了解决问题的方法:

def min_edits(s1, s2):
if len(s1) == 0:
    return len(s2)
if len(s2) == 0:
    return len(s1)
elif s1[0] == s2[0]:
    return min_edits(s1[1:], s2[1:]) #characters match, no additional cost here
else:
    replace = min_edits(s1[1:], s2) + 1  # Insert into second string
    insert = min_edits(s1, s2[1:]) + 1  # Insert into first string
    delete = min_edits(s1[1:], s2[1:]) + 1  # replace/remove from both strings
    return min(
        insert,
        replace,
        delete
    )