Как я могу написать этот метод, чтобы он подходил для оптимизации хвостовой рекурсии?

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


}

Спасибо! * * 1004

Answer 1

Я предполагаю, что вы спрашиваете, потому что у вас действительно есть реальная проблема с раздачей стека.Похоже, что вы делаете здесь строковую манипуляцию, повторяющуюся на подстроке на одну меньшую.Это потенциально крайне неэффективно и опасно.Строки могут быть настолько длинными, что рекурсивный алгоритм разрушает стек, и поскольку строки неизменяемы, но не постоянны, вы создаете новую строку каждый раз, когда вызываете подстроку;это создаст минимум O (n ^ 2) байтов строк, которые необходимо скопировать вокруг.

(Кроме того, похоже, что вы делаете какой-то шаблон с самой длинной совпадающей подпоследовательностью;Вполне вероятно, что какая-то стратегия запоминания поможет справиться со сложностью времени, что часто делает с такой проблемой.)

Чтобы решить проблему размещения строк, вы можете обойти вместо строки,строка и индекс, который должен рассматриваться как начало строки.Теперь вы просто увеличиваете целое число, а не выделяете и копируете строку.

Чтобы решить проблему рекурсии, вы можете использовать ряд методов.Я написал серию статей о различных способах превращения простых рекурсивных алгоритмов в алгоритмы, которые используют кучу вместо пространства стека вызовов.Некоторые из них написаны на JScript, но идеи легко переносятся на C #.

Наконец, в C # 5 мы введем ключевое слово «await», которое заставляет компилятор выполнять преобразование стиля передачи продолжения в программе.,Цель этого ключевого слова - облегчить асинхронное программирование, но побочным эффектом этого является то, что оно значительно упрощает программирование без стеков.Если вам интересно, загрузите выпущенный нами предварительный выпуск Community Technology Preview, и вы можете автоматически преобразовать свою программу в программу, не требующую стека.

ОК, так что статьи по превращению рекурсивных алгоритмов в алгоритмы, которыепотреблять кучу, а не стек, начните здесь:

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/

Answer 2

Вроде. Вы можете сделать любой рекурсивный алгоритм хвостово-рекурсивным, неловко, преобразовав его в стиль продолжения . Эффект состоит в том, чтобы просто взять стек вызовов и передать его явно. Но это не принесет вам пользы, о которой вы, вероятно, думаете, а именно, чтобы иметь возможность отбрасывать предыдущее состояние после рекурсивных вызовов для экономии места. Вы просто помещаете государство в другое место.

Реальный вопрос может быть следующим: можете ли вы изменить какой-либо рекурсивный алгоритм так, чтобы он требовал только постоянного пространства, возможно, с помощью хвостовой рекурсии? Ответ, конечно, может быть. Как правило, рекурсивные функции, использующие древовидную рекурсию (где рекурсивные вызовы разветвляются на несколько более глубоких рекурсивных вызовов), могут быть трудно преобразовать таким образом. Ваш алгоритм соответствует этому описанию.

(Первоначально я предложил запоминать match или использовать DP для этой проблемы, что ускорило бы его, но я думаю, что на самом деле это не сэкономило бы ваше пространство. Ну, хорошо.)

Answer 3

Простой способ - использовать цикл while(true).Пример:

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

Этот процесс обычно известен как TCE (или удаление хвостовых вызовов).

Обновление:

Я пропустил || в конце.Вы не можете преобразовать это, поскольку никакие вызовы для соответствия не находятся в хвостовой позиции.|| требует оценки результата перед возвратом.Метод может быть переписан, чтобы избежать этого.

Answer 4

C # не поддерживает текущую хвостовую рекурсию. См. Этот связанный вопрос по этому вопросу

Также ознакомьтесь с этой статьей MSDN , посвященной аналогичной технике, называемой trampolining * 1007.*