Reordering arguments using recursion (pro, cons, alternatives)

Question

I find that I often make a recursive call just to reorder arguments.

For example, here's my solution for endOther from codingbat.com:

Given two strings, return true if either of the strings appears at the very end of the other string, ignoring upper/lower case differences (in other words, the computation should not be "case sensitive"). Note: str.toLowerCase() returns the lowercase version of a string.

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

I'm very comfortable with recursions, but I can certainly understand why some perhaps would object to it.

There are two obvious alternatives to this recursion technique:

Swap a and b traditionally

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());
}

• Not convenient in a language like Java that doesn't pass by reference
• Lots of code just to do a simple operation
• An extra if statement breaks the "flow"

Repeat code

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

• Explicit symmetry may be a nice thing (or not?)
• Bad idea unless the repeated code is very simple
  • ...though in this case you can get rid of the ternary and just || the two expressions

---

So my questions are:

• Is there a name for these 3 techniques? (Are there more?)
  • Is there a name for what they achieve? (e.g. "parameter normalization", perhaps?)
• Are there official recommendations on which technique to use (when)?
• What are other pros/cons that I may have missed?

---

Another example

To focus the discussion more on the technique rather than the particular codingbat problem, here's another example where I feel that the recursion is much more elegant than a bunch of if-else's, swaps, or repetitive code.

// 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 };
}

Recursion and ternary operators don't bother me as much as it bothers some people; I honestly believe the above code is the best pure Java solution one can possibly write. Feel free to show me otherwise.

Answer 1

For this particular example, I wouldn't use anything you suggested.. I would instead write:

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

While the ternary operator does have its place, the if statement is often more intelligible, especially when the operands are fairly complex. In addition, if you repeat code in different branches of an if statement, they will only be evaluated in the branch that is taken (in many programming languages, both operands of the ternary operator are evaluated no matter which branch is selected). While, as you have pointed out, this is not a concern in Java, many programmers have used a variety of languages and might not remember this level of detail, and so it is best to use the ternary operator only with simple operands.

One frequently hears of "recursive" vs. "iterative"/"non-recursive" implementations. I have not heard of any particular names for the various options that you have given.

In any case, my recommendation would be to do as little in each statement as possible. The more things that you do in a single statement, the more confusing it will be for others who need to maintain your code.

In terms of your complaint about repetitiion... if there are several lines that are being repated, then it is time to create a "helper" function that does that part. Function composition is there to reduce repitition. Swapping just doesn't make any sense to do, since there is more effort to swap than to simply repeat... also, if code later in the function uses the parameters, the parameters now mean different things than they used to.

EDIT
My argument vis-a-vis the ternary operator was not a valid one... the vast majority of programming languages use lazy evalution with the ternary operator (I was thinking of Verilog at the time of writing, which is a hardware description language (HDL) in which both branches are evaluated in parallel). That said, there are valid reasons to avoid using complicated expressions in ternary operators; for example, with an if...else statement, it is possible to set a breakpoint on one of the conditional branches whereas, with the ternary operator, both branches are part of the same statement, so most debuggers won't split on them.

Answer 2

It is slightly better to use another method instead of recursion

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());
}

Answer 3

Let’s first establish that code duplication is usually a bad idea.

So whatever solution we take, the logic of the method should only be written once, and we need a means of swapping the arguments around that does not interfere with the logic.

I see three general solutions to that:

1. Your first recursion (either using if or the conditional operator).
2. swap – which, in Java, is a problem, but might be appropriate in other languages.
3. Two separate methods (as in @Ha’s solution) where one acts as the implementation of the logic and the other as the interface, in this case to sort out the parameters.

I don’t know which of these solutions is objectively the best. However, I have noticed that there are certain algorithms for which (1) is generally accepted as the idiomatic solution, e.g. Euklid’s algorithm for calculating the GCD of two numbers.

I am generally averse to the swap solution (2) since it adds an extra call which doesn’t really do anything in connection with the algorithm. Now, technically this isn’t a problem – I doubt that it would be less efficient than (1) or (3) using any decent compiler. But it adds a mental speed-bump.

Solution (3) strikes me as over-engineered although I cannot think of any criticism except that it’s more text to read. Generally, I don’t like the extra indirection introduced by any method suffixed with “Impl”.

In conclusion, I would probably prefer (1) for most cases although I have in fact used (3) in similar circumstances.

Answer 4

Another +1 for "In any case, my recommendation would be to do as little in each statement as possible. The more things that you do in a single statement, the more confusing it will be for others who need to maintain your code."

Sorry but your code:

// 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 };
}

It's perhaps for you the best "pure java code", but for me it's the worst... unreadable code, if we don't have the method or the comment we just can't know at first sight what it's doing...

Hard to read code should only be used when high performances are needed (but anyway many performances problems are due to bad architecture...). If you HAVE TO write such code, the less you can do is to make a good javadoc and unit tests... we developper often don't care about implementation of such methods if we just have to use it, and not to rework it... but since the first sight doesn't tell us what is does, we can have to trust it works like we expect it does and we can loose time...

Recursive methods are ok when it's a short method, but i think a recursive method should be avoided if the algorithm is complex and if there's another way to do it for almost the same computation time... Particulary if other peoples will prolly work in this method.

For your exemple it's ok since it's a short method, but anyway if you'r just not concerned by performances you could have used something like that:

// 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();
}

A simple way to implement your method, easily readable by all java >= 1.5 developper, that works for 1 to n integers... Not the fastest but anyway if it's just about speed use c++ or asm :)