Java Selection of a recursive function

Question

I have 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 line length of 5000, this is the program output:

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

Now why is a function with a double function call ~ 3x faster? How should I structure my recursive functions for maximum speed in Java?

Answer 1

This is a question of a good old algorithmic analysis. Your reverse1 should execute at O ​​(n logn) time, while reverse2 needs O (n²) time, so the longer the line for the reverse, the more dramatically faster than reverse2 will be reverse1 .

It is not the number of calls that dominates the use of resources, but the time spent copying the characters into a new String object created with each string concatenation operation. String concatenation in reverse2 works on longer strings on average than in reverse1 , so its full runtime is longer.

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

• In reverse2 each character is copied several times, equal to its position in the original string (± 1, which does not bother me). This makes n / 2 copies on average for each character.

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

Answer 2

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

Other calls will go faster, because on average they will concatenate shorter lines, making a difference of 3 times.

Answer 3

@HenningMakholm's answer is excellent, but I just wanted to throw it away based on the comment about iterative methods and immutable strings from @cHao. This would probably be most suitable for comment, but I wanted space real estate to respond ...

 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 at the end creates only one immutable String object and works in O(n) , gives 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