Рекурсивные структуры данных

Рекурсивными могут быть не только предложения, но и структуры дан-

ных. Турбо Пролог является единственным широко используемым языком прог-

раммирования, который позволяет определить типы рекурсивных данных. Тип

данных является рекурсивным, если он допускает структуры, содержащие та-

кие же структуры, как и они сами.

Наиболее важным рекурсивным типом данных является список, но мы не

будем рассматривать списки в этой главе. Подробности обработки списков,

как встроенного в Пролог средства, мы обсудим в Главе 8. В этой главе мы

определим рекурсивный тип данных, опишем его и используем для написания

удивительно быстрой сортирующей программы.

Структурой вводимого нами типа данных является дерево (Рис.7). Важ-

но, чтобы каждая ветвь дерева сама являлась деревом, поэтому структура

рекурсивна.

|

|

|

Cathy

/ \

/ \

/ \

/ \

/ \

Michael Melody

/ \ / \

/ \ / \

Charles Hazel Jim Eleanor

Рисунок 7.1: Часть фамильного дерева