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

Question

As a first attempt to get into merge sort i produced the following code which works on strings because they are easier than lists to deal with.

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

Reading on Wikipedia about possible optimizations i found the following hint "To make sure at most O(log N) space is used, recurse first into the smaller half of the array, and use a tail call to recurse into the other." but honestly i have no idea how to apply this to my case. I have some vague memories of tail calls from my IT class when we were taught about recursion and factorials but i really can't understand how to apply Wikipedia's advice to my piece of code.

Any help would be much appreciated.

Answer 1

There are numerous problems with this question, starting with the fact that you've implemented a very slow version of QuickSort but asked a question about MergeSort. MergeSort is not typically implemented as a tail recursive algorithm.

Let me ask a better question on your behalf:

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

Let me sketch out a simpler tail-recursive transformation and then you can work out how to apply that to your sort, should you decide that doing so is a good idea.

Suppose you have the following recursive algorithm:

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

Let's break that down into more steps using the following somewhat bizarre transformation:

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

Notice that this is exactly the same program as before, just more verbose. Of course you would not write the program in such a verbose manner, but it will help us make it tail recursive.

The point of tail recursion is to turn a recursive call into a goto. We can do that like this:

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

See what we've done there? Instead of recursing, we reset the current reference to the thing that would have been recursed on, and go back to the start, while maintaining the state of the accumulator.

Now is it clear how to do the same thing to the QuickSort algorithm?

Answer 2

This looks like a less-than-optimal variant of QuickSort, not a MergeSort. You are missing a C# equivalent of this part:

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result