Java Choosing a recursive function

Question

I have here two different recursive functions for reversing a string in Java:

    Long ms1 = System.currentTimeMillis();
    String str1 = reverse1(str);
    ms1 = System.currentTimeMillis() - ms1;

    Long ms2 = System.currentTimeMillis();
    String str2 = reverse2(str);
    ms2 = System.currentTimeMillis() - ms2;

    System.out.println("Input: " + str);
    System.out.println("  Length: " + str.length());
    System.out.println("Reverse 1:");
    System.out.println("  " + herp + " function calls");
    System.out.println("  " + ms1 +  " milliseconds");
    System.out.println("Reverse 2:");
    System.out.println("  " + derp + " function calls");
    System.out.println("  " + ms2 +  " milliseconds");
}
public static String reverse1(String str){
    herp++;
    if(str.length() == 1) return str;
    return reverse1(str.substring(str.length()/2)) + reverse1(str.substring(0, str.length()/2));
}
public static String reverse2(String str){
    derp++;
    if(str.length() == 1) return str;
    return reverse2(str.substring(1)) + str.charAt(0);
}

Given a string of length 5000, this is the program's output:

Input: ...
  Length: 5000
Reverse 1:
  9999 function calls
  16 milliseconds
Reverse 2:
  5000 function calls
  52 milliseconds

Now why is the function with double the function calls ~3x faster? How should I be structuring my recursive functions for max speed in Java?

Answer 1

That's a matter of good old algorithmic analysis. Your reverse1 should run in O(n logn) time, whereas reverse2 needs O(n²) time, so the longer the string to reverse is, the more dramatically faster than reverse2 will reverse1 be.

The resource usage is dominated not by the number of calls, but by the time taken to copy characters into the new String object created at each string concatenation operation. The string concatenation in reverse2 works on longer strings on average than the one in reverse1, so its total execution time is longer.

• In reverse1, every character is copied log2(n) times (where n is the length of the original string), since the depth of the recursive call tree is about log2(n).

• In reverse2 every character is copied a number of times equal to its position in the original string (±1, which I don't care about). That makes n/2 copies on average of each character.

For large n, log2(n) is much smaller than n/2, and therefore reverse1 tends to be faster.

Answer 2

Roughly 50% of the calls of the first type end without doing any work, because str.length() == 1. This makes the number of calls with non-trivial work roughly equal. If you move derp++ and herp++ calls to after the exit condition, you'd get the number of "non-trivial" calls, and they will be equal.

Other calls will go faster, too, because on average they would be concatenating shorter strings, making up for the 3x difference.

Answer 3

@HenningMakholm's answer is excellent, but I just wanted to throw this out there, based on a comment about iterative methods and immutable strings by @cHao. This would probably be most appropriate for a comment but I wanted the space real estate of an answer...

public static String reverse3(String str){
    StringBuilder sb = new StringBuilder();
    int i;
    for(i = str.length() - 1; i >= 0; i--) {
        sb.append(str.charAt(i));
    }
    return sb.toString();
}

This iterative method which creates only one immutable String object at the end, and runs in O(n) time yields the following results:

  Length: 5406
Reverse 1:
  10811 function calls
  59 milliseconds
  5406 length correctness test
Reverse 2:
  5406 function calls
  126 milliseconds
  5406 length correctness test
Reverse 3:
  3 milliseconds
  5406 length correctness test