Search code examples
javarecursionreturn

Needless return in recursive method

I am writing a recursive code that counts the minimum number of operations we need to do in order that s2 is equals to s1, the valid operations are insert 1 character (di), delete 1 character (dc) and dn stays for do nothing

private static int editDistance(String s1, String s2) {

    if((s2.isEmpty() && (dn == 0 && dc == 0 && di == 0)) || (s1.isEmpty() && (dn == 0 && dc == 0 && di == 0)))
        return Integer.max(s1.length(), s2.length());

    if(s2.isEmpty()) {
        return 0;
    } else if(s1.isEmpty()) {
        dc++;
        return 1 + editDistance(s1, rest(s2));
    } else if(s1.charAt(0) == s2.charAt(0)) {
        dn++;
        return editDistance(rest(s1), rest(s2));
    } else if(s1.charAt(0) != s2.charAt(0) && dc <= di) {
        dc++;
        return 1 + editDistance(s1, rest(s2));
    } else if(s1.charAt(0) != s2.charAt(0) && dc > di) {
        di++;
        return 1 + editDistance(rest(s1), s2);
    }

    return 0;

}

For instance if we have s1 = "home" and s2 = "hote" there will be 1 delete operation (for 't'), 1 insert operation ('m') and 3 do nothing operations.

The problem is that my statements are annidated in those if/else if branches so for my program to compile i had to put a return 0 statement at the bottom which is pointless, how could i correct this?

Solution

  • If these conditions exhaust all possibilities, I would advise you not to remove any conditions (because that's documentation of why the program does what it does), but rather throw an exception - for instance AssertionError with message "this can't happen".

    That's because sometimes due to refactoring or magic, things which should not happen DO happen, and it's best not to ignore them but to crash the application instead (since it's in an inconsistent state).

    Java compiler simply can't always detect impossible scenarios (it would be computationally too expensive, and in some cases - impossible - see "halting problem").