7
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ As an aside: it's easier to recursively reverse a linked list. (Depending on the situation, this may be important.) \$\endgroup\$ – apnorton Oct 15 '14 at 22:26
10
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Also note that C# does not have tail recursion optimisation \$\endgroup\$ – BlueTrin Oct 16 '14 at 12:12
  • \$\begingroup\$ @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. \$\endgroup\$ – rolfl Oct 16 '14 at 12:17
  • \$\begingroup\$ @BlueTrin C# doesn't, but .Net does, though only under certain circumstances (e.g. x64 vs. x86). \$\endgroup\$ – svick Oct 17 '14 at 14:10
7
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – rolfl Oct 15 '14 at 17:00
4
\$\begingroup\$

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];
…
\$\endgroup\$
  • \$\begingroup\$ I think "tail call elimination" is the more commonly used term. \$\endgroup\$ – mjolka Oct 15 '14 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.