Python programming:

Exercise IX$.$ The edit distance between two strings is a measure of their simi$-$

larity$-$the smaller the edit distance, the more similar the strings are with regard

to the minimum number of insert, delete and substitute operations needed to

transform one string into the other.

Consider the strings kitten and sitting. The first string can be transformed

into the second string with the following operations: Substitute the $k$ with an

$s,$ substitute the $e$ with an $i,$ and insert a $g$ at the end of the string. This is the

smallest number of operations that can be performed to transform kitten into

sitting. As a result, the edit distance is $3.$

Write a recursive function that computes the edit distance between two

strings. Use the following algorithm:

Let $s$ and $t$ be the strings

Use your recursive function to write a program that reads two strings from

the user and displays the edit distance between them.