c# - 我如何编写此方法才能使其符合尾递归优化的条件？

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

我所有关于continuation passing风格的文章都在这里:(从底部开始)

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

关于异步的在这里:(同样，从底部开始)

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