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