Recursive String Inverse Function

Question

writing a recursive return line function out of curiosity, but with few problems with XOR. The whole point of this function is not to use an iterator, so 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); } 

Jamble seems to be the first part of my line

"Hey stop!" becomes "I ♫ → A ← E↨reht yeh"

it is always the first half of a phrase that is messed up ...

UPDATE ..

I believe that XOR is not needed here .. so the base job is used, also got rid of the 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

If you want to use a solution that uses XOR and recursion, try the following:

 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 do not need to return anything, since everything is done in an array. Of course, you could just delete the XOR part and just swap the elements, but this is much cooler .;)

(edit: index should start at 0)

Answer 2

Recursion is almost always used to simplify tasks. Recursive algorithms are usually functional in nature (although they are not necessary).

In the case of reversing the string (or char[] ), “simpler” means “work with a smaller array”.

For example, you can reduce the following:

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

(data are shown on the left, section data are on the right).

In pseudo code, 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 will leave it to you to figure out what needs to be done next with the data that you have.

Answer 3

Most likely not the most efficient, but this should give you some ideas on how to make recursion work ...

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

Answer 4

One observation: you are working and returning an array. Always the same array. An array is always a reference.

This means that your return statement is complex and misleading. Just end with return arr; in all cases.

Consider part of a common hint: simplify it and you will see errors easier. That -- only in the returned expression 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; } 

Answer 5

In this particular example, I would rather do this:

 return arr.Reverse(); 

Answer 6

XOR needs to be called twice to swap a pair of elements. It is called only once in the first half of the array. (As amended: strictly speaking, it receives only once for each assignment, so the network effect is similar to performing two-XOR swaps on half the array.)