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?

• apnorton: As an aside: it's easier to recursively reverse a linked list. (Depending on the situation, this may be important.)

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

• BlueTrin: Also note that C# does not have tail recursion optimisation
• rolfl: @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.
• svick: @BlueTrin C# doesn't, but .Net does, though only under certain circumstances (e.g. x64 vs. x86).

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

• rolfl: 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.

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];
...

• mjolka: I think "tail call elimination" is the more commonly used term.