Какие есть способы удаления рекурсии зачем это применяется

Устранение левой рекурсии

Содержание

Определение:

Говорят, что контекстно-свободная (КС) грамматика [math]\Gamma[/math] содержит непосредственную левую рекурсию (англ. direct left recursion), если она содержит правило вида [math]A \to A\alpha[/math] .

Определение:

Говорят, что КС-грамматика [math]\Gamma[/math] содержит левую рекурсию (англ. left recursion), если в ней существует вывод вида [math]A \Rightarrow^* A\alpha[/math] .

Методы нисходящего разбора не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида [math]A \Rightarrow^* A\alpha[/math] может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

Устранение непосредственной левой рекурсии [ править ]

Опишем процедуру, устраняющую все правила вида [math]A \to A\alpha[/math] , для фиксированного нетерминала [math]A[/math] .

1. Запишем все правила вывода из [math]A[/math] в виде: [math]A \to A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m [/math] , где
   • [math]\alpha[/math] — непустая последовательность терминалов и нетерминалов ( [math]\alpha \nrightarrow \varepsilon [/math] );
   • [math]\beta[/math] — непустая последовательность терминалов и нетерминалов, не начинающаяся с [math]A[/math] .
2. Заменим правила вывода из [math]A[/math] на [math]A \to\beta_1A^\prime \mid \ldots\ \mid \beta_mA^\prime \mid \beta_1 \mid \ldots \mid \beta_m[/math] .
3. Создадим новый нетерминал [math] \to \alpha_1 \mid \ldots \mid \alpha_n \mid \alpha_1 \mid \ldots \mid \alpha_n[/math] .

Изначально нетерминал [math]A[/math] порождает строки вида [math]\beta\alpha_\alpha_ \ldots \alpha_[/math] . В новой грамматике нетерминал [math]A[/math] порождает [math]\beta[/math] , а [math]A^\prime[/math] порождает строки вида [math]\alpha_\alpha_ \ldots \alpha_[/math] . Из этого очевидно, что изначальная грамматика эквивалентна новой.

Пример [ править ]

[math]A \to S\alpha \mid A\alpha[/math]

[math]S \to A\beta[/math]

Есть непосредственная левая рекурсия [math]A \to A\alpha[/math] . Добавим нетерминал [math]A^\prime[/math] и добавим правила [math]A \to S\alpha>[/math] , [math] A^ <\prime>\to \alpha> [/math] .

[math]A \to S\alpha> \mid S\alpha[/math]

[math]S \to A\beta[/math]

В новой грамматике нет непосредственной левой рекурсии, но нетерминал [math]A[/math] леворекурсивен, так как есть [math] A \Rightarrow S\alpha> \Rightarrow A\beta\alpha> [/math]

Алгоритм устранения произвольной левой рекурсии [ править ]

Воспользуемся алгоритмом удаления [math] \varepsilon [/math] -правил. Получим грамматику без [math] \varepsilon [/math] -правил для языка [math]L(\Gamma) \setminus \lbrace \varepsilon \rbrace[/math] .

Упорядочим нетерминалы, например по возрастанию индексов, и будем добиваться того, чтобы не было правил вида [math]A_i \to A_j\alpha[/math] , где [math]j \leqslant i[/math] . Если данное условие выполняется для всех [math]A_i[/math] , то в грамматике нет [math]A_i \Rightarrow^* A_i[/math] , а значит не будет левой рекурсии.

Пусть [math]N = \lbrace A_1, A_2, \ldots , A_n \rbrace[/math] — упорядоченное множество всех нетерминалов.

Если [math]\varepsilon[/math] присутствовал в языке исходной грамматики, добавим новый начальный символ [math]S'[/math] и правила [math]S’ \to S \, \mid \, \varepsilon [/math] .

После [math]i[/math] итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида [math]A_k \to A_l\alpha, k \lt i[/math] , должно быть [math]l \gt k[/math] . В результате при следующей итерации внутреннего цикла растет нижний предел [math]m[/math] всех продукций вида [math]A_i \to A_m\alpha[/math] до тех пор, пока не будет достигнуто [math]i \leqslant m [/math] .

После [math]i[/math] итерации внешнего цикла в грамматике будут только правила вида [math]A_i \to A_j\alpha[/math] , где [math]j \gt i[/math] . Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть [math]_i [/math] новый нетерминал. Можно заметить, что нет правила вида [math]\ldots \to _i[/math] , где [math]_i[/math] самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле. Для строгого поддержания инвариантов цикла можно считать, что созданный на [math]i[/math] итерации в процессе устранения непосредственной левой рекурсии нетерминал имеет номер [math]A_<-i>[/math] (т.е. имеет номер, меньший всех имеющихся на данный момент нетерминалов).

На [math]i[/math] итерации внешнего цикла все правила вида [math]A_i \to A_j \gamma[/math] где [math] j \lt i [/math] заменяются на [math]A_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma[/math] где [math]A_j \to \delta_1 \mid \ldots \mid \delta_k[/math] . Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

Оценка времени работы [ править ]

Пусть [math]a_i[/math] количество правил для нетерминала [math]A_i[/math] . Тогда [math]i[/math] итерация внешнего цикла будет выполняться за [math]O\left(\sum\limits_ a_j\right) + O(a_i)[/math] , что меньше чем [math]O\left(\sum\limits_^n a_j\right)[/math] , значит асимптотика алгоритма [math]O\left(n\sum\limits_^n a_j\right)[/math] .

Худший случай [ править ]

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

[math]A_1 \to 0 \mid 1[/math]

[math]A_ \to 0 \mid 1 [/math] для [math]1 \leqslant i \lt n[/math]

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для [math]A_i[/math] будут представлять из себя все двоичные вектора длины [math]i[/math] , а значит размер грамматики будет экспоненциальным.

Порядок выбора нетерминалов [ править ]

Определение:

Говорят, что нетерминал [math]X[/math] — прямой левый вывод (англ. direct left corner) из [math]A[/math] , если существует правило вида [math]A \to X\alpha[/math] .

Определение:

Левый вывод (англ. left corner) — транзитивное, рефлексивное замыкание отношения «быть прямым левым выводом».

Во внутреннем цикле алгоритма для всех нетерминалов [math]A_i[/math] и [math]A_j[/math] , таких что [math]j \lt i[/math] и [math]A_j[/math] — прямой левый вывод из [math]A_i[/math] заменяем все прямые левые выводы [math]A_j[/math] из [math]A_i[/math] на все выводы из [math]A_j[/math] .

Это действие удаляет левую рекурсию только если [math]A_i[/math] — леворекурсивный нетерминал и [math]A_j[/math] содержится в выводе [math]A_i[/math] (то есть [math]A_i[/math] — левый вывод из [math]A_j[/math] ,в то время как [math]A_j[/math] — левый вывод из [math]A_i[/math] ).

Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если [math]j \lt i[/math] и [math]A_j[/math] — прямой левый вывод из [math]A_i[/math] , то [math]A_i[/math] — левый вывод из [math]A_j[/math] . Упорядочим их по уменьшению количества различных прямых левых выводов из них.

Так как отношение «быть левым выводом» транзитивно,то если [math]C[/math] — прямой левый вывод из [math]B[/math] , то каждый левый вывод из С также будет левым выводом из [math]B[/math] . А так как отношение «быть левым выводом» рефлексивно, [math]B[/math] явлеяется своим левым выводом, а значит если [math]C[/math] — прямой левый вывод из [math]B[/math] — он должен следовать за [math]B[/math] в упорядоченном множестве, если только [math]B[/math] не является левым выводом из [math]C[/math] .

Пример [ править ]

[math]A \to S\alpha [/math]

[math]S \to S\beta \mid A\gamma \mid \beta[/math]

Среди правил [math]A[/math] непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит. Во время второй итерации внешнего цикла правило [math] S \to A\gamma [/math] переходит в [math] S \to S\alpha\gamma [/math] .

Грамматика имеет вид

[math]A \to S\alpha [/math]

Устраняем левую рекурсию для [math]S[/math]

Источник

Удаление рекурсии — заглянуть в закулисную теорию

Я новичок в этом сайте, и этот вопрос, конечно, не исследовательский уровень — ну да ладно. У меня есть немного опыта в разработке программного обеспечения и почти нет в CSTheory, но я нахожу это привлекательным. Короче говоря, я хотел бы получить более подробный ответ на следующий вопрос, если этот вопрос приемлем на этом сайте.

Итак, я знаю, что у каждой рекурсивной программы есть итеративный аналог, и я вроде как понимаю популярное объяснение, которое предлагается для нее, поддерживая что-то похожее на «системный стек» и выдвигая настройки среды, такие как адрес возврата и т. Д. Я нахожу этот вид волнистым ,

Будучи немного более конкретным, я хотел бы (формально) посмотреть, как можно доказать это утверждение в тех случаях, когда у вас есть функция, вызывающая цепочку . Кроме того, что если существуют некоторые условные операторы, которые могут привести к вызову F i некоторого F j ? То есть граф вызовов потенциальных функций имеет несколько сильно связанных компонент. F 0 → F 1 … F i → F i + 1 … F n → F 0 ‘ role=»presentation»> F 0 → F 1 … F i → F i + 1 … F n → F 0 F i ‘ role=»presentation»> F i F j ‘ role=»presentation»> F j

Я хотел бы знать, как можно справиться с этими ситуациями, скажем, с помощью рекурсивного итеративного преобразователя. И действительно ли этого ручного описания, о котором я говорил ранее, достаточно для этой проблемы? Я имею в виду, почему я считаю, что удаление рекурсии в некоторых случаях легко. В частности, удалить рекурсию из обхода бинарного дерева по предварительному заказу очень просто — это стандартный вопрос интервью, но удаление рекурсии в случае почтового заказа всегда было для меня кошмаром.

Что я действительно спрашиваю, так это вопроса 2 ‘ role=»presentation»> 2

(1) Есть ли действительно более формальное (убедительное?) Доказательство того, что рекурсия может быть преобразована в итерацию?

(2) Если эта теория действительно существует, то почему я нахожу, например, итерацию предзаказа проще, а поступорядочения так сложно? (кроме моего ограниченного интеллекта)

Источник

Устранение рекурсии в Python

Привет, Хабр! Представляю вашему вниманию перевод статьи «Removing a recursion in Python, part 1» автора Эрика Липперта (Eric Lippert).

На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.

В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.

Недавний вопрос на StackOverflow заставил меня задуматься, как преобразовать рекурсивный алгоритм в итеративный, и оказалось, что Python довольно подходящий язык для этого.
Проблема с которой столкнулся автор вопроса заключалась в следующем:

• Игрок находится в произвольной клетке на пронумерованном поле;
• Цель вернуться в клетку №1;
• Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
• Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.

Вопрос заключается в следующем: какое наименьшее количество монет необходимо заплатить, чтобы вернуться из текущей клетки в первую.

Задача имеет очевидное рекурсивное решение:

Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?

Перед тем как мы начнем, хочу отметить, что конечно существуют более быстрые решения этой конкретной задачи, сама по себе она не очень интересна.

Скорее эта задача послужила лишь отправной точкой в вопросе, как в общем случае избавиться от единственного рекурсивного вызова в программе на Python.

Смысл в том, что можно преобразовать любой простой рекурсивный метод и избавиться от рекурсии, а это всего лишь пример, который оказался под рукой.

Техника, которую я собираюсь показать, конечно не совсем соответствует тому, как принято писать на Python, вероятно решение в Python-стиле использовало бы генераторы или другие возможности языка.

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

Для начала давайте посмотрим как привести программу к такой форме.

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

Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:

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

Обратите внимание, что вспомогательная функция возвращает функцию.

Теперь запишем это в более общей и краткой форме:

Видно, что каждое проделанное изменение сохраняло смысл программы.

Сейчас проверка на чётность числа выполняется дважды, хотя до изменений проверка была одна.

Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.

Но давайте не будем беспокоиться об этом в рамках решения этой задачи.

Мы свели наш рекурсивный метод до максимально общей формы.

• В базовом случае:
  • вычисляем значение, которое нужно вернуть;
  • возвращаем его.
• В не базовом случае:
  • вычисляем аргумент рекурсии;
  • производим рекурсивный вызов;
  • вычисляем возвращаемое значение;
  • возвращаем его.

Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost .

Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.

Если у вас 2 и более рекурсии, то нам понадобится другое решение.

Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.

Хитрость в том, чтобы представить, что происходит в рекурсивной программе.

Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.

То есть, все вызовы get_argument происходят перед всеми вызовами after.
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:

Больше никакой рекурсии!

Выглядит как магия, но все что мы здесь делаем — то же самое, что делала рекурсивная версия программы и в том же порядке.

Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!

Единственная полезная информация в стеке вызовов в рекурсивной версии программы — это какое значение имеет after, поскольку эта функция вызывается следующей, а все остальное на стеке не важно.

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

В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.

Источник