使用递归重新排序参数（优点、缺点、替代方案）

Question

我发现我经常进行递归调用只是为了重新排序参数。

例如，这是我对codingbat.com 的 endOther 的解决方案：

给定两个字符串，如果其中一个字符串出现在另一个字符串的最末尾，则返回true，忽略大小写差异（换句话说，计算不应该“区分大小写”） ”）。注意：str.toLowerCase() 返回字符串的小写版本。

public boolean endOther(String a, String b) {
  return a.length() < b.length() ? endOther(b, a)
    : a.toLowerCase().endsWith(b.toLowerCase());
}

我对递归非常满意，但我当然可以理解为什么有些人可能会反对它。

对于这种递归技术，有两种明显的替代方法：

传统上交换 a 和 b

public boolean endOther(String a, String b) {
  if (a.length() < b.length()) {
    String t = a;
    a = b;
    b = t;
  }
  return a.toLowerCase().endsWith(b.toLowerCase());
}

• 对于像 Java 这样不通过引用传递的语言来说并不方便
• 大量代码只是为了执行简单的操作
• 额外的 if 语句破坏了“流程”

重复代码

public boolean endOther(String a, String b) {
  return (a.length() < b.length())
    ? b.toLowerCase().endsWith(a.toLowerCase())
    : a.toLowerCase().endsWith(b.toLowerCase());
}

• 显式对称性可能是一件好事（或不是？）
• 坏主意，除非重复的代码非常简单
  • ...尽管在这种情况下您可以去掉三元，而只使用 || 两个表达式

---

所以我的问题是：

• 这 3 种技术有名称吗？ （还有更多吗？）
  • 他们所取得的成就有一个名称吗？ （例如“参数标准化”，也许？）
• 是否有关于使用哪种技术（何时）的官方建议？
• 我可能错过了哪些其他优点/缺点？

---

另一个例子

为了将讨论更多地集中在技术而不是特定的codingbat问题上，这里有另一个例子，我觉得递归比一堆if-else、交换或重复代码要优雅得多。

// sorts 3 values and return as array
static int[] sort3(int a, int b, int c) {
    return
      (a > b) ? sort3(b, a, c) :
      (b > c) ? sort3(a, c, b) :
      new int[] { a, b, c };
}

递归和三元运算符并不像某些人那样困扰我。老实说，我相信上面的代码是人们可以编写的最好的纯 Java 解决方案。请随意向我展示其他情况。

Answer 1

让我们首先确定代码重复通常是一个坏主意。

因此，无论我们采取什么解决方案，该方法的逻辑都应该只编写一次，并且我们需要一种在不干扰逻辑的情况下交换参数的方法。

我看到了三种通用的解决方案：

1. 您的第一次递归（使用 if 或条件运算符）。
2. swap – 这在 Java 中是一个问题，但在其他语言中可能是合适的。
3. 两种独立的方法（如 @Ha 的解决方案），其中一个充当逻辑的实现，另一个充当接口，在本例中用于整理参数。

我不知道这些解决方案中哪一个客观上是最好的。然而，我注意到某些算法通常将 (1) 视为惯用解决方案，例如用于计算两个数字的 GCD 的 Euklid 算法。

我通常不喜欢交换解决方案 (2)，因为它添加了一个额外的调用，而该调用实际上并没有执行与算法相关的任何操作。现在，技术上这不是问题 - 我怀疑使用任何像样的编译器它的效率都会低于（1）或（3）。但它增加了精神上的减速。

解决方案（3）给我的印象是过度设计，尽管我想不出任何批评，除了它需要阅读更多的文字。一般来说，我不喜欢任何以“Impl”为后缀的方法引入的额外间接。

总之，在大多数情况下我可能更喜欢（1），尽管我实际上在类似情况下使用了（3）。

Answer 2

另一个+1表示“无论如何，我的建议是在每个语句中尽可能少地做事。在单个语句中做的事情越多，对于需要维护代码的其他人来说就越令人困惑。”

抱歉，你的代码：

// sorts 3 values and return as array
static int[] sort3(int a, int b, int c) {
    return
      (a > b) ? sort3(b, a, c) :
      (b > c) ? sort3(a, c, b) :
      new int[] { a, b, c };
}

这可能对你来说是最好的“纯java代码”，但对我来说这是最糟糕的......不可读的代码，如果我们没有方法或注释，我们第一眼就无法知道什么它正在做...

难以阅读的代码应该只在需要高性能时使用（但无论如何，许多性能问题都是由于糟糕的架构...）。如果你必须编写这样的代码，那么你能做的就是制作一个好的javadoc和单元测试......如果我们只需要使用它而不是返工的话，我们开发人员通常不关心这些方法的实现...但是由于第一眼并没有告诉我们它的作用，我们必须相信它会像我们期望的那样工作，并且我们可以节省时间...

当它是一个简短的方法时，递归方法是可以的，但我认为如果算法很复杂并且有另一种方法可以在几乎相同的计算时间内完成它，则应避免使用递归方法......特别是如果其他人可能会使用这种方法。

对于你的例子来说，它是一个简短的方法，但无论如何，如果你不关心性能，你可以使用类似的东西：

// sorts int values
public static int[] sort(Integer... intValues) {
    ArrayList list = new ArrayList(
    for ( Integer i : intValues ) {
      list.add(i);
    }
    Collections.sort(list);
    return list.toArray();
}

一种简单的方法来实现你的方法，所有java> = 1.5开发人员都可以轻松阅读，适用于 1 到 n 个整数...
不是最快的，但无论如何，如果只是为了速度，请使用 c++ 或 asm :)

Answer 3

对于这个特定的例子，我不会使用你建议的任何东西。我会写：

public boolean endOther(String a, String b){
    String alower=a.toLowerCase();
    String blower=b.toLowerCase();
    if ( a.length() < b.length() ){
        return blower.endsWith(alower);
    } else {
        return alower.endsWith(blower);
    }
} 

虽然三元运算符确实有它的位置，但 if 语句通常更容易理解，特别是当操作数相当多时复杂的。此外，如果您在 if 语句的不同分支中重复代码，则它们只会在所采用的分支中进行计算（在许多编程语言中，三元运算符的两个操作数都会被计算，无论哪个）已选择分支）。虽然，正如您所指出的，这在 Java 中不是一个问题，但许多程序员使用过多种语言，并且可能不记得这种详细程度，因此最好仅对简单的操作数使用三元运算符。

人们经常听说“递归”与“迭代”/“非递归”实现。我没有听说过您所提供的各种选项的任何特定名称。

无论如何，我的建议是在每个声明中尽可能少做任何事情。您在一条语句中执行的操作越多，对于需要维护您的代码的其他人来说就会越混乱。

就您对重复的抱怨而言......如果有几行被重复，那么是时候创建一个“帮助器”函数来完成该部分。函数组合的目的是减少重复。交换没有任何意义，因为交换比简单地重复需要更多的努力......而且，如果函数后面的代码使用参数，那么参数现在的含义与以前不同。

编辑
我关于三元运算符的论点不是有效的......绝大多数编程语言都使用三元运算符的惰性求值（在撰写本文时我正在考虑 Verilog，它是一种硬件描述语言（ HDL），其中两个分支并行评估）。也就是说，有充分的理由避免在三元运算符中使用复杂的表达式；例如，使用 if...else 语句，可以在其中一个条件分支上设置断点，而使用三元运算符，两个分支都是同一语句的一部分，因此大多数调试器不会在它们上进行拆分。

Answer 4

使用其他方法代替递归稍微好一些

public boolean endOther(String a, String b) {
    return a.length() < b.length() ? endOtherImpl(b,a):endOtherImpl(a,b);
}

protected boolean endOtherImpl(String longStr,String shortStr)
{
    return longStr.toLowerCase().endsWith(shortStr.toLowerCase());
}