Reversing a string in-place - recursion or iteration?

Question

I am practicing my recursion skills as I think I am really weak in this area.

I have written the following Java class whose purpose is to reverse a string but to do it 'in-place' - i.e. no additional arrays. I have two implementations - one iterative and one recursive. Why would I choose one implementation over the other?

Also, does my recursive solution use tail call optimization?

public class TestRecursion {
 public static void reverseIter(char[] in) {
 int start = 0;
 int end = in.length - 1;
 while(start < end) {
 swap(start, end, in);
 start ++;
 end--;
 }
 System.out.println("iteration result: "+in);
 }
 public static char[] reverseRecur(char[] in, int start, int end) {
 if (end < start) return in;
 else {
 swap(start, end, in);
 return reverseRecur(in, ++start, --end);
 }
 }
 private static void swap(int start, int end, char[] input) {
 char c1 = input[start];
 char c2 = input[end];
 input[start] = c2;
 input[end] = c1;
 }
 public static void main(String[] args) {
 char[] input = "testy".toCharArray();
 reverseIter(input);
 char[] input2 = "testy".toCharArray();
 char[] out = reverseRecur(input2, 0, input2.length-1);
 System.out.println("recursive result: "+out);
 }
}

• itsbruce: The JVM doesn't support full TCO and javac doesn't even attempt the partial TCO simulation that Scala uses. Java is not a good language to use recursion in.
• 200_success: Move your S.o.println() out of reverseIter() into main(), not just for consistency with reverseRecur(), but also because it is a good habit to write functions without side effects whenever possible.

Answer 1

First some clean-up is needed on your code. The iterative method first:

• do not call System.out.println("iteration result: "+in); as this will do a toString() on in and you will get something like iteration result [C@b312fca6. Use the following instead: System.out.println("iteration result: " + Arrays.toString(in));
• start and end are not great names because, after the first loop, they no longer represent the start and end positions. Consider left and right as alternatives.

• In this case, a double-value for loop is a good candidate for readability:

  for (int left = 0, right=in.length - 1; left < right; left++, right--) {
   swap(left, right, in);
  }
  

• alternatively, a single value iteration could be useful:

  for (int i = (in.length - 1) / 2; i >= 0; i--) {
   swap(i, in.length - 1 - i, in);
  }
  

in the recursive call, you have some other problems:

• The character array is passed in, and modified in place. There is no reason to return it as well. The method should return void.
• you should simplify the condtitional statement to make the tail-recursion obvious... since the true part of the if condition returns from the method, there is no need for an else block
• you should not be modifying the actual start and end values 'in place' as this requires some extra work. In the recursive call you can simply do start + 1 instead of ++start.
• I prefer using the final keyword on recursive components to make sure you only modify what you should be....

Consider the recursive method:

 public static void reverseRecur(final char[] in, final int left, final int right) {
 if (left >= right) {
 return;
 }
 swap(left, right, in);
 reverseRecur(in, left + 1, right - 1);
 }

Now the 'tail' part is obvious.

As for whether tail-call optimization is performed, I don't know. I expect that the compiler may completely re-write this recursive function as an iteration..... which leads on to the next question: Which one is better?

In this case, the iterative solution is best. It has the least impact on resources (stack space), and will be fastest. It is also the most intuitive (readable).

Your iterative solution would be preferable

• Simon Forsberg: I actually think the while is more readable than the double-value for (I guess I'm just used to for-loops having one iteration variable). Besides this, nice review.
• 200_success: Strings don't read left-to-right in some languages.
• rolfl: @200_success true, but, left and right refer to the array indices, and will work equally well for character arrays that contain right-to-left text.
• 200_success: Programmers who work with right-to-left text might not think of arrays as being laid out left-to-right either. ☺︎

Answer 2

Some nitpicks about your reverseRecur().

I would name the parameters beginIndex and endIndex. The alternative pair would be start – finish, but C++ chooses begin – end, so I think it would be more conventional.

Another convention in Java (and most languages with 0-based arrays) is to use inclusive-exclusive intervals. That is, begin would be the index of the first character to be included in the reversal, and end would be one greater than the index of the last character to be included in the reversal. This convention is used, for example, with String.substring(int beginIndex, int endIndex). It's also nice to remove the -1 from main().

public static char[] reverseRecur(char[] in, int beginIndex, int endIndex) {
 if (endIndex <= beginIndex) return in;
 swap(in, beginIndex, endIndex);
 return reverseRecur(in, ++beginIndex, --endIndex);
}

As for swap(), I would put the arguments in the same order for consistency, but rename the parameters. There is no sense of "beginning" or "ending" when swapping two elements. By connotation, i and j are array indexes. You can get away with just one temporary variable.

private static void swap(char[] in, int i, int j) {
 char tmp = in[i];
 in[i] = in[j];
 in[j] = tmp;
}

For consistency, also offer

public static void reverseIter(char[] in, int beginIndex, int endIndex) { ... }

(Alternatively, declare reverseRecur(char[], int, int) to be a private helper to public reverseRecur(char[]).)

---

As for the question of whether iteration or recursion is more appropriate... iteration is almost always preferable in Java (and other languages of the C family). Since there is no support for tail call optimization, recursion will fail for large inputs with a stack overflow. There are some situations where recursion is appropriate: when you have an algorithm that explores a tree and requires backtracking, and you know that the tree depth will be reasonable, and the problem is too complex to convert into an iterative solution.

String reversal isn't one of those situations, but it's good to get some practice with recursion for when you eventually encounter such a situation. ☺︎

Answer 3

In this case Iteration is preferable.

If your input string would cause StackOverflowError exceptions. Besides, iteration would be much faster because it does not require the overhead of creating a stack frame with the parameters, calling the function, and returning the value. Since Java does not support tail recursion, the function call cannot be optimized away.