递归字符串反转函数

Question

写一个递归的字符串反转函数，但在使用异或时遇到了一些问题。整个函数的重点是不使用迭代器，这也是为什么它是一个递归函数。这不是作业，只是出于好奇。

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

看起来它混乱了我的字符串的前半部分

"hey there stack!" 变成了 "I♫→A ←E↨reht yeh"

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

更新..

我想这里并不需要XOR..所以使用了基本赋值，并且去掉了返回。

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

- Sonic Soul

---

@NullUserException - 显然已经足够老了，在问题中引用《南方公园》的歌曲（是否合适是另一个问题）。 - Justin Niessner

我建议将您的字符串更改为更标准的短语，例如：“快速棕色狐狸跳过懒狗”。 - Lucas B

或者是一个回文，比如“aibohphobia”？ - Dr. Wily's Apprentice

你知道 XOR 运算符是做什么的吗？看起来你认为它会交换你的字符，但实际上它的作用是：10110110 XOR 00011100 变成了：10101010，这就是为什么你得到了无意义的结果。 - Jimmy Hoffa

@Jimmy Hoffa：看看结果的尾部... 它对一部分有效。 - H H

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

    // ???
}

我会留给您去思考如何处理您所拥有的数据的下一步操作。

- strager

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

- Edward Leno

---

其实我认为这是我最喜欢的解决方案，因为它只有三行。简单而优雅。 - Sonic Soul

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部分并交换元素，但这样做会显得< strong>不够酷。;)

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

- Marcus Johansson

Answer 4

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

这意味着您的返回语句过于复杂和误导性。在所有情况下，只需以return arr;结束即可。

考虑到这是一般提示的一部分：让它更简单，您将更容易看到错误。返回语句中的--应该引起警惕。

---

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

- H H

---

我不明白我的返回语句有什么问题...我可以将其分解成几行，但它会做完全相同的事情。如果索引为0，则返回arr，否则进行递归。那部分已经测试并且正常工作。 - Sonic Soul

@Sonic：你正在原地反转。你根本不需要返回任何东西。如果你使用了return，它与递归无关，是独立的。 - H H

Answer 5

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

return arr.Reverse();

- Matthew Abbott

---

谢谢，但我并没有询问反转字符串的最佳方法...这只是一个好奇心的练习。 - Sonic Soul

作业结果肯定应该要求最简洁的答案... - Matthew Abbott

这是关于编程的内容，请将其翻译成中文。请仅返回已翻译的文本：这不是作业。我曾经在面试中被问到过这个问题，但并不需要编写代码...现在出于好奇心写下它。 - Sonic Soul

@Sonic Soul，在我看来，那仍然属于“家庭作业”的范畴。你需要稍微指导一下正确的方向，而不是直接给出问题的完整答案。 - strager

Answer 6

XOR 必须被调用两次才能交换一对元素。在数组的前半部分中，它只会被调用一次。(在编辑中：严格来说，每个赋值只会被调用一次，因此其净效果类似于在数组的一半上执行两个 XOR 交换。)

- TechNeilogy