Reversing a string in-place - recursion or iteration?

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

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

StackExchange Code Review Q#39147, answer score: 5