1. Member
Join Date
Oct 2010
Posts
35
Rep Power
0

## 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

Java 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 ) ;

}

}```

2. Senior Member
Join Date
Apr 2010
Location
Philippines
Posts
580
Rep Power
7
What error it throws? Kindly post its stacktrace

3. Member
Join Date
Oct 2010
Posts
35
Rep Power
0
actually its a logic error, im running it through an IDE and it
Java 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
Java 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

4. Senior Member
Join Date
Apr 2010
Location
Philippines
Posts
580
Rep Power
7
All of your return is inside an if statement, what distanceB method will return when it did not meet any of your if statement.
Java 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. :)

5. Senior Member
Join Date
Jan 2011
Location
Bangalore, India
Posts
102
Rep Power
0
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.

6. Member
Join Date
Oct 2010
Posts
35
Rep Power
0
okay so i have fixed my recursive part... or so i thought but its throwing a OutOfMemoryError.. anybody know whats up? Heres my code
Java 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
Java 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)```

7. Senior Member
Join Date
Apr 2010
Location
Philippines
Posts
580
Rep Power
7
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
Java 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]
}```

8. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
7
Nice to see my sig gets used as an analogy :)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•