recursive string reverse function

Question

writing a recursive string reverse function out of curiosity, but having a bit of problem with XOR there. The whole point of this function, is to not use iterator, which is why it is a recursive function. this is not homework, just curiosity.

    private static char[] ReverseNL(char[] arr, int index)
    {
        var len = arr.Length;
        if (index > 0)
            arr[len - index] ^= arr[index - 1];
        return index-- < 1 ? arr : ReverseNL(arr, index);
    }

it seems to jamble the first part of my string

"hey there stack!" becomes "I♫→A ←E↨reht yeh"

it is always the first half of the phrase that gets jumbled...

UPDATE..

i suppose XOR wasn't really needed here.. so used basic assignment, also got rid of return.

    private static void ReverseNL(char[] arr, int index) {
        var len = arr.Length;
        if (index > 0 && index > len / 2) {
            var c = arr[len - index];
            arr[len - index] = arr[index - 1];
            arr[index - 1] = c;
            index--;
            ReverseNL(arr, index);
        }
    }

Answer 1

In this particular example, I'd rather do this:

return arr.Reverse();

Answer 2

Recursion is almost always used to make problems simpler. Recursive algorithms are typically functional in nature as well (though they don't have to be).

In the case of reversing a string (or a char[]), "simpler" means "operating on a smaller array".

For example, you can reduce as follows:

"test"
"est"   't'
"st"    'e'
"t"     's'
""      't'

(On the left is the data reduced; on the right is the cut data).

In pseudocode, you can perform the reduction as follows:

char[] reverse(char[] data) {
    if (data.Count() == 0) {
        return new char[] { };
    }

    char cut = data.First();
    char[] rest = data.Skip(1);

    char [] restReversed = reverse(rest);

    // ???
}

I'll leave it up to you to figure out what needs to be done next with the data you have.

Answer 3

The XOR has to be called twice to swap a pair of elements. It is only getting called once on the first half of the array. (In edit: strictly speaking, it's only getting called once for each assignment, so net effect is like doing a two-XOR swap on half the array.)

Answer 4

If you want a solution which uses XOR and recursion, try this:

private static void ReverseNL(char[] arr, int index)
{
    if (index <arr.Length/2)
    {
        arr[index] ^= arr[arr.Length - index-1];
        arr[arr.Length - index-1] ^= arr[index ];
        arr[index] ^= arr[arr.Length - index-1];
        ReverseNL(arr,++index);
    }
}

You don't need to return anything, since everything is done in the array. Of course you could just remove the XOR-part and just swap the elements, but this is much cooler. ;)

(edit: index should start at 0)

Answer 5

Likely not to be the most efficient, but this should give you some ideas on how to get the recursion working ...

    static string ReverseNL (string s)
    {
        if ((s == null) || (s.Length <= 1))
        {
            return s;
        }
        return ReverseNL(s.Substring(1)) + s[0];
    }

    static void Main(string[] args)
    {
        string src = "The quick brown fox";
        Console.WriteLine(src);
        src = ReverseNL(src);
        Console.WriteLine(src);
    }