оператором цикла с параметром (for) и массивом. Выбор двух или более вариантов выражается условным иливьт рающим оператором и соответственно записью с вариантам И наконец, повторение неизвестное (потенциально бесконе ное) количество раз выражается оператором цикла с ппр' условием (while) или с постусловием (repeat). CooTBeTciBviS щая структура данных - последовательность (файл)-jI стейший вид структуры, допускающей построение типор с бесконечным кардинальным числом.

Возникает вопрос: а существует ли структура данных, ко торая подобным же образом соответствует оператору пр цедуры? Разумеется, наиболее интересная и новая по сравне нию с другими операторами особенность процедур -это воз можность рекурсии. Значения типа данных, который можно тгазБЯТБ~ рекурсивным, должны содержать одну или более компонент того же типа, что и все значение, по аналогии с процедурой, содержащей один или более вызовов самой себя. Как и в процедурах, в таких определениях типов ре-курсия может быть прямой или косвенной.

Простой пример объекта, тип которого можно определить рекурсивно, - арифметическое выражение, встречающееся в языках программирования. Рекурсия отражает возможность вложенности, т. е. использования заключенных в скобки подвыражений в качестве операндов в выражении. Итак, пусть выражение здесь определяется неформально следующим образом:

Выражение состоит из терма, за которым следует знак операции, за которым следует терм. (Эти два терма являются операндами соответствующей операции.) Терм- это либо переменная, представ.пснная идентификатором, либо выражение, заключенное в скобки.

Тип данных, значениями которого являются подобные выражения, легко можно описать с помощью известного уже средства - рекурсии*). .

Ьт expression ~ гешй ор: operatori opdL Gpdl: term. Old;

tyjpe term = record

if t then (Jd: alfa)

else (subex: expression)

(4.1)

*) Описание типа term в (4.1) не принадлежит языку Паскаль: в не используется конструкция if ... then ... else для выражения варна в записи. Более правильной с точки зрения Паскаля была бы форМУ^

4.1..Рекуpctieme-типы данных

т

каждзя переменная типа term состоит;из двух компог 1.поля признака t и, если t истинно, поля id, иначе -

(4.2)

Рис. 4.1. Расположение в памяти рекурсивных записей.

поля subex. Теперь рассмотрим в качестве примеров следующие четыре выражения: .

.Г. .1. х + у .

: 2. x-iy*z) .3. {x + y)*{z - w)

4. {x/{y+z))*w

Эти выражения можно представить, как показано на рис. (4.1), на котором, наглядно видна их вложенная, рекур-

type /ел/п == record

case/: Boolean ot , . true: (id: alfa) -. ..

, false: (subex: expression) end

Днакр зацикливание в описаниях типов: term определяется через ех-Ра, expression через term - обычно также запрещается. Таким об-К^. подобного рода рекурсивные описания типов в Паскале не приме-1тся. Для построения динамических структур в нем используется аппа-/р1инамического размещении переменных и ссылок, описанный ниже.-Н

сивная структура. Эти схемы определяют также размещу этих выражений в памяти.

Другой пример рекурсивной информационной структур, генеалогическое дерево. Пусть генеалогическое дерево

стоит из имени человека и генеалогических деревьев его дителей. Такое определение \\{ бежно приводит к бесконечн. структуре. Реальные генеалогиц ские деревья конечны, потому 4. на каком-то уровне сведения предках отсутствуют, Если вновь используем рекурсивн\ структуру, как показано в (4.:, то этот факт мы можем учесть:

Рис. 4.2. Структура генеалогического дерева.

type ped - record

if known thcH {name: alfa; father, mother: pt

(4.3)

(Заметим, что каждая переменная типа ped (от pedigree- ш-неалогическое дерево . - Перев] содержит по крайней мере одну] компоненту - поле признака known { .известен ). Если его значение истинно, то имеются ещ три поля; иначе больше нет полей.) Отдельное значение, обо-

значенное (рекурсивным) конструктором записи

X = {T,Ted,{T,Fred,{T,Adam,{F),{F)),F)), {T,Mary,{F),{T,Eva,{F),{F)))

изображено на рис. 4.2, причем, глядя на рисунок, можн также сделать выводы о возможном расположении данных в памяти. (Так как рассматривается только одно определен^ типа, мы пропускаем идентификатор типа ped перед кa 0 конструктором.)

Здесь очевидна важная роль вариантов: это единственно средство, БЮзволяющее сделать рекурсивную структуру печной, поэтому в рекурсивном определении всегда участвуй*