如何编写此方法以使其符合尾递归优化的条件？

Question

有人知道一个算法来对尾部进行简单的递归吗？更具体地说,您将如何将算法应用于以下代码？

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


}

谢谢!

Answer 1

我假设你问的是因为你实际上有一个真正的问题,吹嘘堆栈.看起来你正在做一个字符串操作,在这里重复一个较小的子串.这可能是非常低效和危险的.字符串可以很容易地长,以至于递归算法会破坏堆栈,并且因为字符串是不可变的但不是持久的,所以每次调用substring时都会创建一个新字符串; 这将创建必须复制的最小O(n ^ 2)字节的字符串.

(另外,看起来你正在做一些最长匹配的子序列模式;正如mquander指出的那样,某种记忆策略可能会有助于时间复杂度;它经常会遇到这种问题. )

要解决字符串分配问题,您可以传递而不是字符串,字符串和将被视为字符串开头的索引.现在你只是递增一个整数,而不是分配和复制一个字符串.

为了解决递归问题,您可以使用许多技术.我写了一系列文章,介绍了将简单的树递归算法转换为使用堆而不是调用堆栈空间的算法的各种方法.其中一些是JScript,但这些想法很容易转换为C#.

最后,在C#5中,我们将引入一个"await"关键字,该关键字使编译器在程序上进行连续传递样式转换.这个关键字的目的是使异步编程更容易,但它的副作用是它使无堆栈编程也更容易.如果您有兴趣,请下载我们发布的社区技术预览版,您可以自动将程序转换为不占用堆栈的程序.

好的,所以,关于将递归算法转换为消耗堆而不是堆栈的算法的文章从这里开始:

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

关于延续传递风格的所有文章都在这里:(从下面开始)

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

异步的那些在这里:(再次,从底部开始)

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