О борьбе с рекурсией

Внимание к языкам функционального и логического программирования (ФП и ЛП) не уменьшается. В этом убеждает недавнее появление языков программирования типа Haskell, а также развитие языков Prolog, ФП и ЛП. Но как бы в противовес этому не ослабевает интерес и к приемам устранения рекурсии. Чем же объясняются столь противоречивые тенденции?

Возрастает интерес к языкам ФП и ЛП, причем особенно к так называемым рекурсивным алгоритмам [1], наиболее характерным для упомянутых языков. С помощью рекурсии зачастую гораздо легче решаются те проблемы, справиться с которыми с применением обычных алгоритмических приемов гораздо тяжелее, что хорошо видно даже при простом сравнении «обычных» алгоритмов с эквивалентными им рекурсивными.

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

О скорости

Скорость работы алгоритмов контролировать достаточно просто. Сразу же следует сказать, что время работы рекурсивного алгоритма будет больше, поскольку при передаче параметров через стек потребуются дополнительные затраты времени. Следовательно, эффективность метода преобразования рекурсивных алгоритмов в автоматную форму из работы [1] сомнительна. Скоростные характеристики порождаемых алгоритмов в лучшем случае останутся на исходном уровне. Однако из-за введения механизма «моделирования» рекурсии они, скорее всего, будут худшими.

И еще один момент. Алгоритмы в автоматной форме будут не такими компактными и, может быть, не такими «удобными», как их рекурсивные аналоги. Значит, не так уж много оснований имеется для того, чтобы преобразовывать рекурсивные алгоритмы ради приобретения свойства «автоматности».

Если же нужно повышать скорость алгоритмов, то имеет смысл просто искать другие пути для решения этой же задачи. Например, обычное «циклическое» вычисление факториала (см. листинг 1, код функции factorial_2) почти в два раза быстрее рекурсивного варианта (функция factorial_1), хотя в нем программа и выглядит гораздо «компактнее».

В листинге 2 приведена объектная автоматная модель вычисления факториала, созданная в рамках конечно-автоматной технологии проектирования программ, реализуемой библиотекой FSA (КА-технология) [2]. В ней использован механизм вложения автоматов [3], реализующий механизм рекурсии совместно с механизмом инкапсуляции данных в объекте. Правда, результаты работы вложенного автомата можно получить лишь на следующем такте его функционирования. В рекурсивном варианте действие y1 выполняет вложение автомата, а в действии y2 уже обрабатывается результат работы вложенного автомата.

С точки зрения скорости данная программа работает примерно в 500 раз медленнее, чем созданная «в лоб», но в определенных ситуациях, в частности при программировании параллельных процессов, может быть оправдано и медленное («автоматное») вычисление факториала. Так, в примере, разработанном во время экспериментов, параллельно вычисляются представленные в рекурсивной автоматной форме функции факториала, функция Аккермана (см. [4]) и ханойские башни. Длительность и подобная параллельная реализация актуальны для процессов/функций, вычисляющихся значительное время. Например, для 100-Мгц Pentium время вычисления функции Аккермана для значения A(3,8) при обычной реализации занимает около 5 с, а для А(3,9) — 20 с (язык — Си++, компилятор — Microsoft Visual C++ 6.0, операционная система — Windows 98). Соответственно на это же время приложение замирает и не отвечает ни на какие поступающие к нему запросы/сообщения от мыши, клавиатуры и т. п., что недопустимо для таких процессов, как управление в реальном времени. Применение FSA, безусловно, увеличивает время вычислений, но зато тогда не возникает эффекта «торможения процессов», остающегося даже при использовании автоматной SWITCH-технологии [см. 1].

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

Кроме того, существуют разные алгоритмические приемы повышения скорости, применяемые для рекурсивных алгоритмов. Например, устранение так называемой остаточной рекурсии и запоминание промежуточных значений функций, привязанных к значению ее аргументов (memorization, tabling). Подробнее с этим можно познакомиться на сайте http://www.softcraft.ru/topic.shtml?key=3 (тема форума — «Функциональное программирование — настоящее и будущее»). Применение таких приемов позволяет значительно (даже в сотни раз !) увеличить скорость вычисления рекурсивной функции.

Необходимо учитывать и то, что быстродействие нынешних программ — показатель интегральный. Так, интенсивный графический вывод (речь идет о Windows) способен резко снизить скорость работы программы. В частности, отображение промежуточных значений увеличило время вычисления функции Аккермана для A(3,3) до 1 с (прежнее значение 0,05 с). Программа в автоматном варианте с этими же параметрами выдала результат в 5,5 раза медленнее. Кстати, после устранения остаточной рекурсии уменьшилось время работы еще в 2 раза, но все же не в 500 раз, о чем было сказано выше. А вот вычисление без пересчета промежуточных значений практически сравняло скорость работы обычной и автоматной программ. Это свидетельствует о том, что у современных вычислительных систем потери, связанные с реализацией графических возможностей, гораздо значительнее, чем можно было бы предполагать.

Реализация рекурсии

При изучении проблемы преобразования рекурсивных программ прежде всего пришлось столкнуться с ограничением объема памяти, выделенной под стек (в обычном варианте) и под внутренние структуры данных (в автоматном варианте). Так, при вычислении функции Аккермана объем стека, необходимый для реализации нужной глубины рекурсии, пропорционален значению функции, и потому уже при вычислении A(3,11) стек переполняется (предыдущее значение для A(3,10) было благополучно вычислено, оно равнялось 8189). Автоматная реализация (речь идет только о FSA) функции Аккермана «обрушилась» при вычислении A(3,7) вследствие ограничения числа автоматных процессов в FSA, причем это происходит независимо от того, параллельные они или вложенные.

Ясно, что рассмотренные проблемы разрешаются довольно просто: «механическим» увеличением объема необходимой для этого памяти (физической или логической), например после «корректировки» ядра FSA удалось вычислить даже значение A(3,11). Более серьезной является проблема возможности построения рекурсии, сводящаяся к определению механизма вложенности программных модулей. Для модели блок-схем и автоматной модели программ в рамках КА-технологии вложение моделей «встроено». В первом случае этому соответствует определение подпрограммы, а во втором — вложенного автомата. Похоже, в рамках SWITCH-технологии проблеме организации иерархической вложенности автоматов уделяется не столь большое внимание, что и порождает методы «моделирования» рекурсии (см. первый метод в [1]).

Вообще говоря, проблема глубины рекурсии достаточно актуальна и на практике стремятся не только к ее конечности, но и к ее минимизации [4]. Что-то при этом приходится делать вручную, а что-то делают автоматически компиляторы, оптимизируя программу и устраняя, например, так называемую остаточную рекурсию. Правда, в последнем случае часто глубина остается прежней, хотя скорость и может несколько увеличиться.

И еще раз о скорости работы программ и алгоритмах. Компиляторы могут распознавать и устранять остаточную рекурсию. Но они пока (?) бессильны придумывать за программиста новые алгоритмы. Даже достаточно простые. Вычисление функции Аккермана с запоминанием промежуточных значений лишь незначительно усложняет алгоритм программы («скелет» алгоритма, что очень важно, остается при этом прежним), но вычисление становится практически мгновенным. Даже автоматный вариант, считавший значение функции для A(3,11) на процессоре Celeron 2 (1,2 ГГц) почти 4 ч, после небольшого преобразования считает его за 3 с! Время обычного варианта стало заметным лишь со значения A(3,11) — 0,05 с , а до этого даже для А(3,10) оно составляло 18 с. Причем если раньше объема стека хватало для вычисления значения только А(3,10), то в новом варианте можно определить даже A(3,12). Для FSA удалось вычислить значение A(3,13) и A(4,1)= 65533 за 12 с. Можно, наверное, экспериментировать и дальше, наращивая объем массива запоминаемых значений, но здесь опять встает проблема увеличения объема стека.

Выводы

Что такое рекурсия, необходима ли она и нужно ли искоренять ее в программах? Здесь сложно что-то добавить к сказанному по этому поводу Никлаусом Виртом [5]. Смысл его высказывания в том, что нужна. А если она требуется, если скорость работы программы имеет малое значение, если не нужно решать проблему параллельного функционирования программных модулей (прежде всего в рамках самого приложения), то вряд ли имеет смысл вообще заниматься устранением рекурсии. Зачем тратить большие усилия на создание более сложных алгоритмов, если проблему можно решить легко, просто (см., например, определение функции Аккермана в [4]) и притом в наиболее естественной для нее форме?