На этом шаге мы рассмотрим способ определения рекурсивности подпрограммы.
Сейчас мы покажем, как путевая матрица ориентированного графа может быть использована для решения вопроса о том, являются ли определенные процедуры в программе рекурсивными.
В некоторых языках программирования программист может задать рекурсивность процедуры в явной форме. В других языках для того, чтобы определить, какие из процедур являются рекурсивными, можно использовать идеи, вытекающие из теории графов.
Вначале необходимо заметить, что рекурсивная процедура необязательно вызывает себя непосредственно. Если процедура P1 вызывает P2, процедура P2 вызывает P3, ..., процедура Pn-1 вызывает Pn и процедура Pn вызывает P1, то процедура P1 является рекурсивной. Подобная форма рекурсии называется косвенной.
Пусть P={P1, P2, P3, ..., Pn} - набор процедур в программе. Построим ориентированный граф, состоящий из вершин, соответствующих элементам P. Ребро из Pi в Pj проведем в графе в том случае, когда процедура Pi вызывает процедуру Pj.
Например, пусть матрица смежностей, соответствующая вызовам, проводимым некоторым набором процедур, имеет вид:
Процедура Pi является рекурсивной, если в графе имеется цикл, содержащий Pi. Такие циклы могут быть обнаружены путем анализа диагональных элементов матрицы достижимости Q графа. Так, Pi является рекурсивной процедурой, если Qii=1. Матрица Q может быть построена с помощью программы 1 из шага 100. В приведенном выше примере она имеет вид:
откуда следует, что процедуры P1, P2 и P4 являются рекурсивными.
Замечание [1, с.132-133].
С задачей определения кратчайших путей в графе тесно связана задача транзитивного замыкания бинарного отношения.
Вспомним, что под бинарным отношением на множестве V мы понимаем множество E, являющееся подмножеством V*V.
Отношение является транзитивным, если удовлетворяется условие: если (x,y) принадлежит E и (y,z) принадлежит E, то (x,z) принадлежит E для произвольных x,y,z, принадлежащих E.
Для произвольного такого отношения мы определяем
E* = {(x,y): в (V,E) существует путь ненулевой длины из x в y}.
Нетрудно заметить, что E* - транзитивное отношение на множестве V и E принадлежит E*. Более того, E* является наименьшим транзитивным отношением, содержащим E, т.е. для произвольного транзитивного отношения F, такого, что E принадлежит F выполняется включение E* принадлежит F.
Отношение E* называется транзитивным замыканием отношения E.
Отметим, что бинарное отношение E, принадлежащее V*V, можно однозначно представить ориентированным графом G=(V,E).
Ориентированный граф называется транзитивным, если из существования дуг (xi,xj) и (xj,xk) следует существование дуги (xi,xk).
Транзитивным замыканием графа G=(X,A) является граф Gtc=(X,AUA'), где A' является минимально возможным множеством дуг, необходимых для того, чтобы граф Gtc был транзитивным. Так как путь от xi к xj в графе G должен соответствовать дуге (xi,xj) в Gtc, то совершенно очевидно, что матрица достижимости R графа G почти полностью совпадает с матрицей смежностей A графа Gtc - надо только в матрице A поставить на главной диагонали единицы.
(1) Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
На следующем шаге мы рассмотрим контуры в ориентированных графах.
