editDistanceRecursion.java

public class EditDistanceProblem { 
 public int editDistanceRecursion(String s1, String s2, int m, int n){
            //If any of the string if empty then number of operations
            //needed would be equal to the length of other string
            //(Either all characters will be removed or inserted)

            if(m==0)
                return n; //all elements will be inserted.
            if(n==0)
                return m; // all elements will be removed.

            //If last characters are matching, ignore the last character
            // and make a recursive call with last character removed.
            if(s1.charAt(m-1)==s2.charAt(n-1))
                return editDistanceRecursion(s1, s2, m-1, n-1);

            //If nothing above worked then we need to try all 3 operations
            //and choose the minimum among them
            return 1 + Math.min(editDistanceRecursion(s1, s2, m, n-1), //Insert
                    Math.min(editDistanceRecursion(s1, s2, m-1, n), // Remove
                            editDistanceRecursion(s1, s2, m-1, n-1))); //Replace
        }
 public static void main(String[] args) {
        String s1 = "horizon";
        String s2 = "horizontal";
        EditDistanceProblem ed = new EditDistanceProblem();
        System.out.println("Minimum Edit Distance -(Recursion): " + ed.editDistanceRecursion(s1, s2, s1.length(), s2.length()));
    }
}