4

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);
        }
    }
8
  • 3
    @NullUserException - Obviously old enough to throw in a reference to a class South Park song in a question (whether it's appropriate or not is another question). Aug 6, 2010 at 14:12
  • 1
    I recommend changing your string to a more standard phrase, like: "The quick brown fox jumps over the lazy dog"
    – Lucas B
    Aug 6, 2010 at 14:13
  • I think you want to perform a swap, and you're trying to do an XOR swap (which fails because you got the algorithm wrong). Just use a simple swap; XOR swap will definitely lead to confusion for those who don't fully understand how it works.
    – strager
    Aug 6, 2010 at 14:32
  • 2
    Or maybe a palindrome, like "aibohphobia"? Aug 6, 2010 at 14:35
  • 1
    Do you know what the XOR operator does? It looks like you think it will swap your charachters, this is what it does: 10110110 XOR 00011100 becomes: 10101010 Thus why you get mumbo jumbo Aug 6, 2010 at 14:38

6 Answers 6

7

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.

6

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);
    }
1
  • actually i think this is my favorite solution, as it is only 3 lines. simple and elegant.
    – Sonic Soul
    Aug 6, 2010 at 15:26
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)

0
1

One observation: You are operating on and returning an array. Always the same array. An array is always a reference.

That means your return statement is overcomplicated and misleading. Just end with return arr; in all cases.

Consider that part of a general hint: make it simpler, and you will see errors easier. That -- in the return statement alone should raise a red flag.


// untested, simplified return
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);

    if (index >= 1)
         ReverseNL(arr, index-1);

    return arr;     
}
2
  • i don't see what is so wrong with my return statement.. i could break it down into few lines, but it would do exactly the same thing. it is returning arr if index is 0, otherwise it recurses. that part is tested and working fine.
    – Sonic Soul
    Aug 6, 2010 at 14:30
  • @Sonic: You are reversing in-place. You don't need a return at all. If you do use return it is independent of the recursion yes/no. Aug 6, 2010 at 14:38
0

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

return arr.Reverse();
4
  • thanks, but i did not ask for the best way to reverse a string.. this is just a curiosity exercise
    – Sonic Soul
    Aug 6, 2010 at 14:15
  • Surely a homework result should be asking for the most concise answer possible... Aug 6, 2010 at 14:17
  • this is not homework. i was once asked this at a interview but was not required to write the code.. so writing it out of curiosity now.
    – Sonic Soul
    Aug 6, 2010 at 14:22
  • 1
    @Sonic Soul, In my mind, that still falls under the realm of 'homework'. You need a slight nudge in the right direction to get you back on track, not a full answer to the problem.
    – strager
    Aug 6, 2010 at 14:36
0

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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