递归字符串反转函数

Question

出于好奇编写了一个递归字符串反转函数，但是那里的 XOR 有点问题。这个函数的重点是不使用迭代器，这就是它是递归函数的原因。这不是作业，只是好奇心。

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

它似乎干扰了我的字符串的第一部分

“嘿，堆栈！”变成“I♫→A←E↨reht yeh”，

这总是短语的前半部分变得混乱......

更新..

我想这里并不真正需要异或..所以使用了基本分配，也摆脱了返回。

    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

递归几乎总是用来使问题变得更简单。递归算法本质上也通常是函数式的（尽管它们不是必须的）。

在反转字符串（或 char[]）的情况下，“更简单”意味着“在较小的数组上操作”。

例如，可以如下进行缩减：（

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

左边是缩减后的数据，右边是剪切后的数据）。

在伪代码中，您可以按如下方式执行缩减：

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

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

    char [] restReversed = reverse(rest);

    // ???
}

我将让您自行决定下一步需要对您拥有的数据执行什么操作。

Answer 2

可能不是最有效的，但这应该给你一些关于如何让递归工作的想法......

    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 3

如果您想要一个使用 XOR 和递归的解决方案，请尝试以下操作：

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

您不需要返回任何内容，因为一切都在数组中完成。当然，您可以删除 XOR 部分并交换元素，但这酷得多。 ;)

（编辑：索引应从 0 开始）

Answer 4

一项观察：您正在操作并返回一个数组。始终相同的数组。数组始终是一个引用。

这意味着您的退货声明过于复杂且具有误导性。在所有情况下都以 return arr; 结尾。

考虑一下一般提示的一部分：让它更简单，你会更容易发现错误。仅 return 语句中的 -- 就应该引发危险信号。

---

// 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

在这个特定的例子中，我宁愿这样做：

return arr.Reverse();

Answer 6

必须调用 XOR 两次才能交换一对元素。它仅在数组的前半部分被调用一次。 （编辑中：严格来说，每次分配只调用一次，因此最终效果就像对一半数组进行两次异或交换。）