Статья опубликована в журнале "Телекоммуникации и информатизация образования", 2002, №5, с.72-99.
(краткая аннотация)
Н.И. Туккель, А.А. Шалыто, Н.Н. Шамгунов
Отсюда можно скачать полный текст статьи в формате pdf (180 кб)
В работе [1] предложен метод преобразования произвольных итеративных программ в автоматные программы, что позволяет реализовать произвольный итеративный алгоритм структурированной программой, содержащей один оператор do-while, телом которого является один оператор switch.
В работах [2,3] приведены примеры преобразований рекурсивных программ в итеративные, однако эти преобразования выполнялись неформально, в связи с отсутствием соответствующего метода.
В настоящей работе такой метод предлагается. Он состоит в преобразовании заданной программы с явной рекурсией в итеративную программу, построенную с использованием автомата Мили. Такие программы, как и в работе [1], будем называть автоматными. Метод иллюстрируется примерами преобразований классических рекурсивных программ, которые приведены в порядке их усложнения (факториал, числа Фибоначчи, ханойские башни, задача о ранце).
Идея метода состоит в моделировании работы рекурсивной программы автоматной программой, явно (также, как и в работах [2,3]) использующей стек. Отметим, что явное выделение стека по сравнению со "скрытым" его применением в рекурсии, позволяет программно задавать его размер, следить за его содержимым и добавлять отладочный код в функции, реализующие операции над стеком.
Отметим, что автоматы, которые строятся с помощью предлагаемого подхода, зависят от глубокой предыстории — в отличие от классических автоматов, переходы из одного из состояний определяются ранее запомненным в стеке номером следующего состояния.