c# - 如何将递归算法转换为尾递归算法？

Question

作为对合并排序的第一次尝试，我编写了以下适用于字符串的代码，因为它们比列表更容易处理。

class Program
{
    static int iterations = 0;
    static void Main(string[] args)
    {            
        string test = "zvutsrqponmlihgfedcba";
        test = MergeSort(test);
        // test is sorted after 41 iterations
    }

    static string MergeSort(string input)
    {
        iterations++;
        if (input.Length < 2)
            return input;
        int pivot = 0;
        foreach (char c in input)
            pivot += c;
        pivot /= input.Length;
        string left = "";
        string right = "";
        foreach (char c in input)            
            if (c <= (char)pivot)
                left += c;
            else
                right += c;            
        return string.Concat(new string[] { MergeSort(left), MergeSort(right) });
    }
}

在维基百科上阅读有关可能优化的内容时，我发现了以下提示“为了确保最多使用 O(log N) 空间，首先递归到数组的较小一半，然后使用尾调用递归到另一半。 “但老实说，我不知道如何将其应用到我的案例中。当我们学习递归和阶乘时，我对 IT 课上的尾调用有一些模糊的内存，但我真的不明白如何将维基百科的建议应用到我的代码段中。

如有任何帮助，我们将不胜感激。

Answer 1

这个问题有很多问题，首先是您实现了一个非常慢的 QuickSort 版本，但问了一个关于 MergeSort 的问题。 MergeSort 通常不作为尾递归算法实现。

让我代表你问一个更好的问题:

How do I turn a recursive algorithm into a tail-recursive algorithm?

让我勾勒出一个更简单的尾递归转换，然后您可以想出如何将其应用于您的排序，如果您认为这样做是个好主意的话。

假设您有以下递归算法:

static int Count(Tree tree)
{
    if (tree.IsEmpty) 
        return 0;
    return 1 + Count(tree.Left) + Count(tree.Right);
}

让我们使用以下有点奇怪的转换将其分解为更多步骤:

static int Count(Tree tree)
{
    int total = 0;
    Tree current = tree;
    if (current.IsEmpty) 
        return 0;
    total += 1;
    int countLeft = Count(current.Left);
    total += countLeft;
    current = current.Right;
    int countRight = Count(current);
    total += countRight;
    return total;
}

请注意，这与之前的程序完全相同，只是更加冗长。当然你不会把程序写得这么冗长，但它会帮助我们让它成为尾递归的。

尾递归的要点是将递归调用变成goto。我们可以这样做:

static int Count(Tree tree)
{
    int total = 0;
    Tree current = tree;

 Restart:

    if (current.IsEmpty) 
        return total;
    int countLeft = Count(current.Left);
    total += 1;
    total += countLeft;
    current = current.Right;
    goto Restart;
}

看看我们在那里做了什么？我们没有递归，而是重置了对本应递归的事物的当前引用，然后回到起点，同时保持累加器的状态。

现在清楚如何对 QuickSort 算法做同样的事情了吗？