Reversing an array recursively

Question

Implementation:

void ReverseArray<T>(T[] a)
{
    ReverseArray(a,0,a.Length-1);
}

void ReverseArray<T>(T[] a,int lo,int hi)
{
    if(lo >= hi) return;

    // swap
    var temp = a[lo];
    a[lo] = a[hi];
    a[hi] = temp;

    ReverseArray(a,lo+1,hi-1);
}

Usage:

int[] arr = {1,2,3,4,5,6,7,8};
ReverseArray(arr); // reverses the array

How can I improve this?

Answer 1

You can improve it by making it a loop instead of a recursive call. There is no need for the recursion, and it limits you in ways that a loop would not (for example, you are limited by your stack size with recursion).

Additionally, the loop implementation is simpler, and probably a bunch faster too.

If you do stick with the recursive call, you should make the recursive method private too.

The loop could be as simple as:

void ReverseArray<T>(T[] a)
{
    for (int lo = 0, hi = a.Length - 1; lo < hi; lo++, hi--)
    {
        var temp = a[lo];
        a[lo] = a[hi];
        a[hi] = temp;            
    }
}

Normally I would take issue with the short variable names, but, in this context, with the generic array data type, a is not too bad of a name.

The only style issue I have other than the a, is that you need space around the operators in your conditions and assignments. The code:

ReverseArray(a,0,a.Length-1);
....
ReverseArray(a,lo+1,hi-1);

should be:

ReverseArray(a, 0, a.Length - 1);
....
ReverseArray(a, lo + 1, hi - 1);

Note, that if the recursive call is required as part of an exercise, then it is implemented correctly/functionally, and I can't see any problems other than the limited size of the array (I would guess about 40,000 elements is too many to handle).

Answer 2

Reinventing the wheel:

First of all, you are aware that there is already a reverse method in the .NET Framework, right? Like stated: no need to reinvent the wheel. Here's link for more info on the Array.Reverse method. Unless you wanted to make your own implementation for whatever reason! :)

Variables:

I don't agree with rolfl. Whether you have long or short code, create a regular or generic method: give your variables a meaningful name. It's good practice and better for maintaining your code.

Recursion vs. Loop:

Here I do agree with rolfl. In this situation, the recursion can be replaced by the loop (not going to write that code again).

Extensions:

Since you make the effort of making a generic method, I'd take it a step further and make it an extension method. Nice for reusability and readability.

Final code:

Here's what the code looks like with all the tips I gave:

public static class Extensions
{
    public static void ReverseArray<T>(this T[] array)
    {
        array.ReverseArray(0, array.Length - 1);
    }

    public static void ReverseArray<T>(this T[] array, int lower, int upper)
    {
        for (int i = lower, j = upper; i < j; i++, j--)
        {
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;            
        }
    }
}

And the usage:

int[] arr = {1,2,3,4,5,6,7,8};
arr.ReverseArray();
//Result: 8 7 6 5 4 3 2 1

int[] arr = {1,2,3,4,5,6,7,8};
arr.ReverseArray(1, 3); 
//Result: 1 4 3 2 5 6 7 8

Note that my tips/code might not be perfect, just trying to make you write better/cleaner code. Hope this helps! ;)

Edit:

Useful tip from rolfl to reuse the parameters instead of creating new variables in the for loop. The loop will now look like this:

for(; lower < upper; lower++, upper--)
{
    var temp = array[lower];
    array[lower] = array[upper];
    array[upper] = temp;
}

Answer 3

Recursion is disfavoured in C# since it doesn't support tail call recursion. You'd get worse performance than a for-loop, and expose yourself to stack overflow.

But, playing along anyway…

It seems to be idiomatic in C# to have

void ReverseArray<T>(T[] a, int startIndex, int length)
{
    …
}

which would be consistent with String.Substring(startIndex, length) and Array.Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length).

---

Instead of

// swap
var temp = …

you could name the variable properly.

var swap = a[startIndex];
…