递归方法中不必要的返回

Question

我正在编写一个递归代码，用于计算我们需要执行的最小操作数，以便s2等于s1，有效操作是insert 1 character (di)，delete 1 character (dc)和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;
}

例如，如果我们有 s1 = "home" 和 s2 = "hote"，那么将有 1 个删除操作(对于 't'(、1 个插入操作 ('m'( 和 3 个什么都不做操作。

问题是我的语句在那些 if/else if 分支中被取消，所以我的程序要编译我不得不在底部放一个毫无意义的return 0语句，我该如何纠正这一点？

Answer 1

如果这些条件用尽了所有可能性，我建议您不要删除任何条件(因为这是程序为什么这样做的文档(，而是抛出异常 - 例如AssertionError消息"这不可能发生"。

这是因为有时由于重构或魔术，不应该发生的事情确实会发生，最好不要忽略它们，而是使应用程序崩溃(因为它处于不一致的状态(。

Java编译器根本无法始终检测出不可能的场景(计算成本太高，在某些情况下 - 不可能 - 请参阅"停止问题"(。

Answer 2

删除最后一个如果。当然，只有当您的情况涵盖所有可能的变体时，您才应该这样做。有时正确的方法是抛出异常，以确保如果您不计算某些内容，则程序不会继续使用不正确的值。

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 {
        di++;
        return 1 + editDistance(rest(s1), s2);
    }
}

Answer 3

您可以通过两种方式解决此问题：

1. 如果您删除最后一个 if 语句，可能会发生另一种可能性

   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);
       }else
           return 0;
   }
   

2. 如果最后一个 if 语句涵盖了所有剩余的可能性，只需将最后一个 if 语句替换为 else 关键字。