SoftCraft
разноликое программирование

Top.Mail.Ru

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

Исходники с автоматной реализацией примеров, рассмотренных в статье плюс авторское решение задачи о ханойской башне (64 кб).

Вячеслав Любченко

Дополненная версия статьи, опубликованной в журнале "Мир ПК", #11, 2002 г.

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

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

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

О скорости

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

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

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

Листинг 1. Программа вычисления факториала

//    рекурсивная модель вычисления факториала    
int factorial_1(int n) { return n?(n*factorial(n-1)):1;  }    

//    блок-схемная модель факториала
int factorial_2(int n) 
{
    int nK=0, nF=1;
    while (nK != n) {
        nK ++; nF *=nK;
    }
    return nF;
}

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

Листинг 2. Рекурсивная автоматная модель вычисления факториала

//    рекурсивная модель вычисления факториала    
class FFactRec : public FRcrsn
{
public:    
    int nF; // факториал
    FFactRec(int n);
    virtual ~FFactRec();
private:
    int nK;     // данные
    int x1();
    void y1();
    void y2();
protected:
    void CallFactorial() { 
        if (pRcrsn) delete pRcrsn;
        pRcrsn = new FFactRec(nK-1);
        pRcrsn->FCall(this);
    };
    int  PrevFactorial() { return ((FFactRec*)pRcrsn)->nF;  };
};
FFactRec::FFactRec(int n) :FRcrsn(TT_FactRec) { nK=n; nF=1;}
FFactRec::~FFactRec() { }
LArc TT_FactRec[] = {
    LArc(”f1”, ”00”, ”x1”,    ”—”),
    LArc(”f1”, ”f2”, ”^x1”,    ”y1”),
    LArc(”f2”, ”00”, ”—”,    ”y2”),
    LArc()
    };
int FFactRec::x1() { return nK==0; }
void FFactRec::y1() { CallFactorial(); }
void FFactRec::y2() { nF = PrevFactorial()*nK; }

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

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

Кроме того, существуют разные алгоритмические приемы повышения скорости, применяемые для рекурсивных алгоритмов. Например, устранение так называемой остаточной рекурсии и запоминание промежуточных значений функций, привязанных к значению ее аргументов (memorization, tabling). Применение таких приемов позволяет значительно (даже в сотни раз !) увеличить скорость вычисления рекурсивной функции.

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

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

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

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

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

Выводы

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

Можно, наверное, экспериментировать и дальше (более подробно о истории появления и анализе функции Аккрекмана см. [6]), увеличивая объем массива запоминаемых значений, но здесь опять возникает проблема стека.

Хочется выразить особую благодарность участникам форума на сайте www.softcraft.ru, которые, по сути, инициировали рассмотренную тему, Михаила Потанина (pm), «подложившего» мне функцию Аккермана, и Игоря Дехтяренко (ИД), оказавшего большое влияние на создание быстрого варианта расчета. Спасибо Руслану Богатыреву, который прислал материал [6], ставший дополнительным стимулом к исследованию темы моделирования и расчета значений функции Аккермана.

Литература

  1. Шалыто А., Туккель Н., Шамгунов Н. Ханойские башни и автоматы // Программирование. 2002. №8.
  2. Любченко В.С. О бильярде с Microsoft C++ 5.0 // Мир ПК. 1998. № 1. С. 202-206. http://www.osp.ru/pcworld/1998/01/202.htm
  3. Любченко В.С. Новые песни о главном - II // Мир ПК. 1998. № 7. С. 112-118. http://www.osp.ru/pcworld/1998/07/112.htm
  4. Толковый словарь по вычислительным системам / Под ред. В. Иллингоута и др.: Пер. с англ. А.К. Белоцкого и др.; Под ред. Масловского. М.: Машиностроение, 1991. 560 с.
  5. Вирт Н. Алгоритмы и структуры данных: Пер с англ. М. Мир, 1989. 360 с.
  6. Gunter Dotzel. The Ackerman function. http://www.modulaware.com/mdlt08.htm