Отсюда можно скачать полный текст статьи в формате pdf (191 кб)
Одной из наиболее известных рекурсивных задач является задача о ханойских башнях [1-5], которая формулируется следующим образом. Имеются три стержня, на первом из которых размещено N дисков. Диск наименьшего диаметра находится сверху, а ниже - диски последовательно увеличивающегося диаметра. Задача состоит в определении последовательности перекладываний по одному диску со стержня на стержень, которые должны выполняться так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы, в конце концов, все диски оказались на другом стержне.
В рассматриваемой работе показано, что применение автоматов [6] позволяет формально переходить к итеративным алгоритмам решения этой задачи, либо строить такие алгоритмы непосредственно. В работах [7,8] приведены примеры преобразований рекурсивных программ в итеративные, однако подходы, обеспечивающие такие преобразования, не формализованы. Настоящая работа призвана устранить этот пробел.
В статье предлагаются три метода. Первый из них обеспечивает формальное построение автоматной программы (программы, построенной с использованием автоматов) на основе раскрытия рекурсии с применением стека. Второй метод также обеспечивает раскрытие рекурсии и состоит в построении автомата, осуществляющего обход дерева действий, выполняемых рекурсивной программой. Третий метод состоит в непосредственном управлении стержнями с помощью автомата и не использует таких абстракций как деревья и стеки. Отметим, что применение каждого из предлагаемых методов для рассматриваемой задачи порождает автоматы с двумя или тремя состояниями, управляющие "объектом управления" с 2N состояниями, возникающими в процессе перекладывания дисков.