CODEWITHSUNDEEP
pythonstring
Amon
Amon

Reputation: 2951

Finding the edit distance of two strings with recursion

I need to use recursion to find the edit distance of two strings, i.e I give the function two arguments(each a different sring). And the function will find the least amount of changes required to change s1 into s2. This is what I have so far:

def edit_distance(s1,s2):
    split1 = list(s1)
    split2 = list(s2)
    count = 0
    pos = 0

    if split1[pos] == split2[pos]:
        pos += 1
    else:
        pos +=1
        count += 1
        edit_distance(s1, s2)

return count #This should be the minimum amount required to match the two strings

Upvotes: 0

Views: 2238

Answers (1)

user3072164
user3072164

Reputation:

I annotated your code to show you the code flow. I hope you understand now why you get the error:

def edit_distance(s1,s2):
    split1 = list(s1)    # Split strings into characters
    split2 = list(s2)
    count = 0            # This variable is local, it is not shared through calls to the function!
    pos = 0              # Same

    if split1[pos] == split2[pos]:   # pos is always 0 here!
        pos += 1                     # pos is incremented anyway, in if but also in else !
    else:
        pos +=1                      # See above
        count += 1                   # count is incremented, now it is 1
        edit_distance(s1, s2)        # recursive call, but with the identical arguments as before! The next function call will do exactly the same as this one, resulting in infinite recursion!

return count    # Wrong indentation here

Your function does not do what you want. In case you are talking about Hamming distance, which is not really clear to me still, here is a sample implementation assuming the lengths of both strings are equal:

# Notice that pos is passed between calls and initially set to zero
def hamming(s1, s2, pos=0):    
    # Are we after the last character already?
    if pos < len(s1):
        # Return one if the current position differs and add the result for the following positions (starting at pos+1) to that
        return (s1[pos] != s2[pos]) + hamming(s1, s2, pos+1)
    else:
        # If the end is already reached, the remaining distance is 0
        return 0

Upvotes: 1

Related Questions