# Recursive Edit Distance, 1 mistake.. help please

• 01-26-2011, 01:13 AM
Recursive Edit Distance, 1 mistake.. help please
Hello Everybody...

Few questions... I am writing this program for school that has to implement both the recursive and dynamic way of editing distance between two strings. I have figured out the dynamic way (levenshtein distance) of editing distance but i am stuck with the recursive... i think it may be a simple little problem but any of your guys help is GREATLY appreciated!
Here is my code

Code:

```public class editDistance {     public static int CALLS;     public static boolean MEMOIZING;   // RECURSIVE:        public static int distanceB(String s1, String s2, int m, int n){             if (n == s2.length()) return s1.length()-m;             if (m == s1.length()) return s2.length()-n;                    if (s1 == s2) return distanceB(s1,s2,m+1,n+1);             if (s1 != s2) {     return 1+Math.min(Math.min(distanceB(s1,s2,m,n+1), distanceB(s1,s2,m+1,n)), distanceB(s1,s2,m+1,n+1));        // this throws an error             } }  public static int distance (String s1, String s2) {             // this is without RECURSION VV             // dynamic programming                         int[][] matrix= new int[s1.length() + 1][s2.length() + 1];     for (int i = 0; i < matrix.length; i++) {             for (int j = 0; j < matrix[i].length; j++) {                 matrix[i][j] = i == 0 ? j : j == 0 ? i : 0;                       if (i > 0 && j > 0) {                     if (s1.charAt(i - 1) == s2.charAt(j - 1))                               matrix[i][j] = matrix[i - 1][j - 1];                                       else                         matrix[i][j] = Math.min(matrix[i][j - 1] + 1, Math.min(                                                                 matrix[i - 1][j - 1] + 1,              matrix[i - 1][j] + 1));                     //CALLS = matrix [i][j];                                 }                                 MEMOIZING= true;                                                                 }                                         }                                 return matrix[s1.length()][s2.length()];                   } // end distance class       public static void main(String[] args) {     System.out.println( "--------------------------------------------------") ;     editDistance.MEMOIZING = false ;     editDistance.CALLS = 0 ;     System.out.println( editDistance.distance("shoes","socks") ) ;     System.out.println( editDistance.CALLS ) ;     System.out.println( "--------------------------------------------------") ;     editDistance.MEMOIZING = true ;     editDistance.CALLS = 0 ;     System.out.println( editDistance.distance("shoes","socks") ) ;     System.out.println( editDistance.CALLS ) ;   } }```
• 01-26-2011, 02:34 AM
mine0926
What error it throws? Kindly post its stacktrace
• 01-26-2011, 02:40 AM
actually its a logic error, im running it through an IDE and it
Code:

``` public static int distanceB(String s1, String s2, int m, int n){             if (n == s2.length()) return s1.length()-m;             if (m == s1.length()) return s2.length()-n;                    if (s1 == s2) return distanceB(s1,s2,m+1,n+1);             if (s1 != s2) {                     return 1+Math.min(Math.min(distanceB(s1,s2,m,n+1), distanceB(s1,s2,m+1,n)), distanceB(s1,s2,m+1,n+1));                    }                     }```
the
Code:

`public static int distanceB(String s1, String s2, int m, int n)`
is underlined asking for a return value....

I just don't know how to implement this using recursion, i dont even know if my return statements are okay
• 01-26-2011, 03:53 AM
mine0926
All of your return is inside an if statement, what distanceB method will return when it did not meet any of your if statement.
Code:

``` private String returnSomeString(int index)  {  if(index == 0)     {  return "you choose zero"     }     //What will be the return if index is not equals to zero(0)?     return "you did not choose zero(0)";  }```
Not really good in explanation, but hope you understand what I am trying to explain here. :)
• 01-26-2011, 04:09 AM
subith86
Hi,

I'm not solving your query now. I want you to know the concept of recursion and implement it by yourself.

I have attached an image - recursion_flow.jsp
It'll give you a clear picture of what a recursive method will do.

after step 1 and 3, the condition inside if is true, so it goes inside, but in step 6, condition is false, so it goes out of the block. This stage ends the recursion. All the steps that follow is some kind of fallback you can say.

recursiveMethod(//some integer);
it should have been
x = recursiveMethod(//some integer);
or
x += recursiveMethod(//some integer);
depending on your logic. Here x is some integer.
• 01-27-2011, 03:58 AM
okay so i have fixed my recursive part... or so i thought but its throwing a OutOfMemoryError.. anybody know whats up? Heres my code
Code:

```public class editDistance {         public static int CALLS;     public static boolean MEMOIZING;     int findMin(int d1,int d2, int d3){             if ( d1 < d2 && d1 < d3)                     return d1;             else if (d1 < d3)                     return d2;             else if (d2 < d3)                     return d2;       else                     return d3;     }         // HERES THE RECURSIVE     public static int distanceB(String s1, String s2){             int d1, d2, d3;                         if (s2.length()==0) return s1.length();             if (s1.length()==0) return s2.length();                                if (s1.length() == s2.length())                                       d1 = distanceB(s1+1, s2+1);             else                     d1 = 1 + distanceB(s1+1, s2+1);             d2 = 1 + distanceB(s1, s2+1);             d3 = 1 + distanceB(s1+1, s2);                         return findMin(d1,d2,d3);                               }     public static int distance (String s1, String s2) {             // this is without RECURSION VV             // dynamic programming                         int[][] matrix= new int[s1.length() + 1][s2.length() + 1];                 for (int i = 0; i < matrix.length; i++) {                         for (int j = 0; j < matrix[i].length; j++) {                                 matrix[i][j] = i == 0 ? j : j == 0 ? i : 0;                                 if (i > 0 && j > 0) {                                         if (s1.charAt(i - 1) == s2.charAt(j - 1))                                                 matrix[i][j] = matrix[i - 1][j - 1];                                                           else                                                 matrix[i][j] = Math.min(matrix[i][j - 1] + 1, Math.min(                                                                 matrix[i - 1][j - 1] + 1, matrix[i - 1][j] + 1));                     //CALLS = matrix [i][j];                                 }                                 MEMOIZING= true;                                                                                         }                                         }                                 return matrix[s1.length()][s2.length()];                   } // end distance class       public static void main(String[] args) {     System.out.println( "--------------------------------------------------") ;     editDistance.MEMOIZING = false ;     editDistance.CALLS = 0 ;     System.out.println( editDistance.distanceB("shoes","socks") ) ;     System.out.println( editDistance.CALLS ) ;     System.out.println( "--------------------------------------------------") ;     editDistance.MEMOIZING = true ;     editDistance.CALLS = 0 ;     System.out.println( editDistance.distance("shoes","socks") ) ;     System.out.println( editDistance.CALLS ) ;   }   } /// End-of-File```
here is my StackTrace
Code:

```-------------------------------------------------- Exception in thread "main" java.lang.OutOfMemoryError: Java heap space         at java.util.Arrays.copyOfRange(Arrays.java:3209)         at java.lang.String.<init>(String.java:215)         at java.lang.StringBuilder.toString(StringBuilder.java:430)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)         at editDistance.distanceB(editDistance.java:28)```
• 01-27-2011, 04:42 AM
mine0926
I remember someone's signiture in this forum, he said: "Ever seen a dog chase its tail, now it is an infinite loop"

This is what happening on your distanceB method. Inside your distanceB method you call distanceB method, it keeps calling distanceB method until it runs out of memory.

Also, in this statement
Code:

```    public static int distanceB(String s1, String s2)     {             int d1, d2, d3;             if (s2.length()==0) return s1.length();             if (s1.length()==0) return s2.length();             [b]         [i]//!it will never reach else statement[/i]             if (s1.length() == s2.length())             d1 = distanceB(s1+1, s2+1);             else             d1 = 1 + distanceB(s1+1, s2+1);             d2 = 1 + distanceB(s1, s2+1);             d3 = 1 + distanceB(s1+1, s2);             return findMin(d1,d2,d3);[/b]     }```
• 01-27-2011, 08:04 AM
m00nchile
Nice to see my sig gets used as an analogy :)