УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Реализация рекурсивных алгоритмов на основе автоматного подхода

Статья опубликована в журнале "Телекоммуникации и информатизация образования", 2002, №5, с.72-99.

(краткая аннотация)

Н.И. Туккель, А.А. Шалыто, Н.Н. Шамгунов

Отсюда можно скачать полный текст статьи в формате pdf (180 кб)

Аннотация

В работе [1] предложен метод преобразования произвольных итеративных программ в автоматные программы, что позволяет реализовать произвольный итеративный алгоритм структурированной программой, содержащей один оператор do-while, телом которого является один оператор switch.

В работах [2,3] приведены примеры преобразований рекурсивных программ в итеративные, однако эти преобразования выполнялись неформально, в связи с отсутствием соответствующего метода.

В настоящей работе такой метод предлагается. Он состоит в преобразовании заданной программы с явной рекурсией в итеративную программу, построенную с использованием автомата Мили. Такие программы, как и в работе [1], будем называть автоматными. Метод иллюстрируется примерами преобразований классических рекурсивных программ, которые приведены в порядке их усложнения (факториал, числа Фибоначчи, ханойские башни, задача о ранце).

Идея метода состоит в моделировании работы рекурсивной программы автоматной программой, явно (также, как и в работах [2,3]) использующей стек. Отметим, что явное выделение стека по сравнению со "скрытым" его применением в рекурсии, позволяет программно задавать его размер, следить за его содержимым и добавлять отладочный код в функции, реализующие операции над стеком.

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

Литература

1. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные //Программирование. 2002. №5. (http://is.ifmo.ru, раздел "Статьи")
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.
3. Стивенс Р. Delphi. Готовые алгоритмы. М.: ДМК, 2001.