Q:

Recursion not terminating even though the base cases are perfect

I've been trying this problem. My idea is to try all the possible combinations and if it works then I would proceed with memoization. But actually the recursion is not stopping. This is my algorithm.
This is the code that I've wrote:
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)

This is the recursion tree :
In that recursion tree first branch is replace and second one is insert and the last branch is delete
An "_" indicates that only one string is empty and the function returns infinity.
So we can clearly see that the tree is getting terminated at all cases.
But still it's saying maximum recursion depth exceeded.
Please tell me where I'm doing wrong. Thank you :)

A:

The problem is that the length of the parameters is not decreasing at every step, which is crucial for the recursive calls to reach the base case. In replace, the length of the both strings stays the same, and in the insert step, the length of one string actually increases. 
So, what do we mean by replace, remove or insert? For example, say we have the strings:
ABCD and DECD

Then if we are looking at index 0, then the replace/remove call would leave us with BCD & ECD, and insert would leave us with either ABCD & ECD, or BCD & DECD. With this approach, the length of at least one string always decreases, so we are guaranteed to reach the base case.
EDIT: The base case was being reached, but there was an issue with the logic, so I've added my approach to the problem:
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
    )

