# Reversing an array recursively

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?

• As an aside: it's easier to recursively reverse a linked list. (Depending on the situation, this may be important.) Commented Oct 15, 2014 at 22:26

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).

• Also note that C# does not have tail recursion optimisation Commented Oct 16, 2014 at 12:12
• @BlueTrin - exactly, I should make that clearer. The lack of tail-recursion optimization is what leads to the stack overflow limitation and the performance issue. With the optimization, the recursive call would essentially be a loop anyway. Commented Oct 16, 2014 at 12:17
• @BlueTrin C# doesn't, but .Net does, though only under certain circumstances (e.g. x64 vs. x86). Commented Oct 17, 2014 at 14:10

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

• Nice call on the Extension implementation, also, you may want to consider reusing the lower and upper variables in the loop instead of adding i and j. Makes the naming in there better too. Commented Oct 15, 2014 at 17:00

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).

// swap

var swap = a[startIndex];