Рекурсия используется в двух случаях: для описания программ, выполнению которых предшествует выполнение их собственной копии и для описания структур данных частично состоящих или определяемых с помощью самих себя. Примерами таких рекурсивных структур данных являются списки и деревья. Например, список можно определить следующим образом: <список>:=<пустой>|<элемент>|<список><элемент>
Достоинство рекурсивного определения объекта состоит в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов.
Бинарные деревья
Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Обычно их называют поддеревьями. В языке Паскаль объявить тип, описывающий бинарное дерево можно следующим образом:
type TreeType = ^Tree;
Tree = record
Element: string;
Left, Right: TreeType;
end;
Здесь Element – элемент, находящийся в вершине, а Left и Right – соответственно левое и правое поддерево.
В языке Пролог бинарное дерево можно задать с помощью тернарного функтора tree(Element, Left, Right):
