Рекурсия как от нее избавиться

Пещера программиста

Страницы

четверг, 17 марта 2011 г.

Опыт отказа от рекурсии

В интернете практически не освещена тема отказа от рекурсии в алгоритмах. Много статей и книг где рассказывается, что такое рекурсия, как ей пользоваться. Но вот как от неё избавится — почти ничего нет.

Итак, рекурсия — это вызов функцией самой себя. Всем известен алгоритм вычисления факториала, классика книг. Все красиво и элегантно, хоть циклом кажется и проще. А уж всевозможные алгоритмы анализа строки и работы с регулярными выражениями. Казалось бы, используй и радуйся.
Но не все так просто. Глубина рекурсии (как много раз функция может вызвать саму себя ) ограничена. Ограничена размером стека. Дело в том, что перед вызовом функцией самой себя, нужно сохранить значения всех локальных переменных, чтобы ими можно было воспользоваться после возвращения. А сохраняется это все в стек. И вот пока в стеке есть место, мы можем углубляться в рекурсию. Все глубже , глубже. Пока не выскочит ошибка — Stack overflow. И все , тушите свет.
Стандартная величина стека примерно 2 мб (для windows программ). Так давайте увеличим размер стека опциями компилятора, делов то. А на сколько увеличить, так чтобы было и не много и не мало? а если запросы растут со временем , постоянно перекомпилировать? А если у вас библиотека, которая использует стек вызвавшей её программы ? И вот тут то и понимаешь, что это не наш метод. Надо как то избавляться от рекурсии.
Вот с этим я и столкнулся в поддерживаемой мной библиотеке Colorer. Алгоритм разбора строки по регулярному выражению был рекурсивный. Так же был красив и пах. Но на длинных строках любил падать. Дай строку в 3000 символов и все, приехали. Надо было что то делать.
Единственным методом ликвидации рекурсии, который я нашел , это избавление от хвостовой рекурсии. Суть его в следующем — если рекурсивный вызов идет последним в функции, то функцию можно заменить на цикл. Факториал как раз является примером для этого.
Но у меня рекурсивных вызовов было очень много в функции. Часть можно было развернуть в цикл, но это совсем малая часть. Да и кстати, код был построен так, что в зависимости от результата вызова (функция возвращала bool значение) функция могла завершится или продолжить работу далее. А сама функция была циклом внутри которого switch.
Вот тут то приходит единственное оставшееся решение — а почему бы нам не воспроизвести рекурсивный вызов с помощью цикла и сохранения параметров? т.е. сделать это все вместо компилятора. Что нам для этого нужно:

1. список локальных переменных, которые нужно сохранить.
2. динамический список типа стека, в который мы будем сохранять значения локальных переменных, и извлекать от туда
3. после-рекурсионные действия , или action (не знаю как назвать это лучше)
4. цикл

В начале остановимся на action. Каждый рекурсионный вызов в зависимости от результат приводил к return true, или return false, или return результат_функции, или к продолжению работы функции многими строками кода. Т.к. мы избавляемся от рекурсии в пользу цикла, то этот код нужно выполнить после завершения цикла для этого рекурсионного вызова. Т.е. когда цикл придет к return . Потому все такие ситуации выделяем в один switch, присваивая им свой код action.

Создаем функцию, которая сохраняет локальные переменные,а на их место задает новые (если есть параметры при вызове рекурсии). Как их сохранять, это отдельная песня. У меня было их мало, и я передавал их по ссылке. Помимо переменных нужно сохранить и действие (action) которое нужно сделать в зависимости от результат функции. Эта функция заменяет нам рекурсионный вызов — сохраняем текущие значения, заменяем их на новые. После сохранения мы должны вернутся в начало цикла, как будто мы только зашли в функцию.
Далее, создаем функцию проверки нашего стека на наличие там записей и извлечения их из него. Она нам потребуется для замены строк return чего_то_там . Передаем в неё это чего_то_там . И если стек пустой, возвращаем action = чего_то_там , иначе извлекаем из стека данные, обновляем локальные переменные и возвращаем action в зависимости от чего_то_там. По этому action выполняем код.
Ну а дальше это все объединяем в один цикл и работаем.

В общем описание получилось очень сумбурное, малопонятное. Но объяснить тяжело. Проще показать результат. Правилась функция CRegExp::lowParse. До изменений файлы были следующими cregexp.cpp, cregexp.h. После применения данного метода cregexp.cpp, cregexp.h .

В ходе испытаний, подтвердилась стабильная работа на длинных строках. Код работает корректно. Но немного упала скорость. На тестовых файлах скорость работы упала на 1 секунду (на моем компьютере). После анализа в профайлере, выяснилось , что узким местом стала работа с памятью в нашем стеке. Оптимизированный вариант приведен выше, как финальный. В нем падение скорости составляет уже примерно 0.4 секунды. Но это уже не устранимо. Зато мы не падаем на рекурсии.

В новой версии FarColorer будет применен этот патч. И проблема, зафиксированная во многих баг-репортах , наконец таки уйдет.

Источник

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

Содержание

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

Говорят, что контекстно-свободная (КС) грамматика [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]

Источник

Устранение рекурсии в 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.

Источник