How can I write this method so that it is eligible for tail recursion optimization?

Question

Does someone know of an algorithm to make a simple recursion to a tail one? More specificaly, how would you apply the algorithm to the following code?

namespace Testing
{
    class Program
    {
        static void Main(string[] args)
        {
           Console.WriteLine(match("?**", "aaa"));
           Console.WriteLine(match("*#*?", "aa1$a1a1"));
           Console.WriteLine(match("*#*", "aa11"));
           Console.WriteLine(match("??*", "0110"));
           Console.WriteLine(match("", "abc"));
           Console.WriteLine(match("???", ""));
           Console.ReadLine();

        }


        public static bool match(string p, string s)
        {
            if (p.Length == 0)
                return true;
            if (p.Length > s.Length)
                return false;

            bool firstLetterMatches = false;
            char nextCharInStr = s[0];
            switch (p[0])
            {
                case '*':
                    firstLetterMatches = 'a'<= nextCharInStr && nextCharInStr <= 'z';
                    break;

                case '#':
                    firstLetterMatches = '0'<= nextCharInStr && nextCharInStr <= '9';
                    break;

                case '?':
                    firstLetterMatches = ('a'<= nextCharInStr && nextCharInStr <= 'z') ||
                                         ('0'<= nextCharInStr && nextCharInStr <= '9');
                    break;

                default:
                    return false;
            }

            return match(p,s.Substring(1)) ||  
                (firstLetterMatches && match(p.Substring(1),s.Substring(1)));
        }
    }


}

Thanks!

Answer 1

I'm assuming that you're asking because you actually have a real-world problem with blowing the stack. It looks like you're doing a string manipulation here recursing on one-smaller substrings. This is potentially extremely inefficient and dangerous. Strings can easily be so long that the recursive algorithm blows the stack, and because strings are immutable but not persistent, you're creating a new string every time you call substring; that's going to create minimum O(n^2) bytes of strings that have to be copied around.

(Also, it looks like you're doing some sort of longest-matching-subsequence pattern; as mquander points out, it is likely that some sort of memoization strategy will help with the time complexity; it often does with this sort of problem.)

To solve the string allocation problem you can pass around instead of a string, a string and the index that is to be treated as the beginning of the string. Now you're merely incrementing an integer, rather than allocating and copying a string.

In order to solve your recursion problem, there are a number of techniques you can use. I wrote a series of articles about various ways to turn simple tree-recursive algorithms into algorithms that consume heap instead of call stack space. Some of them are in JScript, but the ideas are easily translatable to C#.

Finally, in C# 5 we will be introducing an "await" keyword which causes the compiler to do a continuation passing style transformation on the program. The intention of this keyword is to make asynchronous programming easier, but a side effect of it is that it makes stackless programming much easier too. If you're interested, download the Community Technology Preview that we've released, and you can automatically transform your program into one that consumes no stack.

OK, so, the articles on turning recursive algorithms into algorithms that consume heap, not stack, start here:

http://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx

All my articles on continuation passing style are here: (start from the bottom)

http://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/

And the ones on the asynchrony are here: (again, start from the bottom)

http://blogs.msdn.com/b/ericlippert/archive/tags/async/

Answer 2

Sort of. You can make any recursive algorithm tail-recursive, awkwardly, by converting it into continuation-passing style. The effect is just to take the call stack and pass it around explicitly. But that won't give you the benefit you're probably thinking of, which is to be able to discard prior state after recursive calls to save space. You're just putting the state somewhere else.

The real question might be: Can you change any recursive algorithm to require only constant space, potentially by way of using tail recursion? The answer, of course, is maybe. Typically, recursive functions that use tree recursion (where recursive calls branch into multiple deeper recursive calls) might be hard to transform this way. Your algorithm fits this description.

(I initially suggested memoizing match or using DP for this problem, which would speed it up, but I guess that wouldn't actually save you space. Oh well.)

Answer 3

The simple way is to using a while(true) loop. Example:

public static bool match(string p, string s)
{
  while (true)
  {
    // normal code
    ...
    // tail call handling
    // instead of return match(x, y)
    var t1 = x; // need to use temps for evaluation of x
    var t2 = y; // same here
    p = t1;
    s = t2;
    continue; 
  }
}

This process is commonly known as TCE (or tail call elimination).

Update:

I missed the || at the end. You cannot convert this, as no calls to match are in a tail position. || requires the result to be evaluated before returning. The method could be perhaps rewritten to avoid that.

Answer 4

C# doesn't current support tail recursion See this related question on the matter

Also check out this msdn article on a similar technique called trampolining