dynamic information structures recursive data types in chap the arrayrecordand set structures were introduced as fundamental data structures they are called fundamental because they constitute the building blocks out of which more complex structures are formedand because in practice they do occur most frequently the purpose of defining data typeand of thereafter specifying that certain variables be of that typeis that the range of values assumed by these variablesand therefore their storage patternis fixed once and for all hencevariables declared in this way are said to be static howeverthere are many problems which involve far more complicated information structures the characteristic of these problems is that not only the values but also the structures of variables change during the computation they are therefore called dynamic structures naturallythe components of such structures are -at some level of resolution -statici of one of the fundamental data types this is devoted to the constructionanalysisand management of dynamic information structures it is noteworthy that there exist some close analogies between the methods used for structuring algorithms and those for structuring data as with all analogiesthere remain some differencesbut comparison of structuring methods for programs and data is nevertheless illuminating the elementaryunstructured statement is the assignment of an expression' value to variable its corresponding member in the family of data structures is the scalarunstructured type these two are the atomic building blocks for composite statements and data types the simplest structuresobtained through enumeration or sequencingare the compound statement and the record structure they both consist of finite (usually smallnumber of explicitly enumerated componentswhich may themselves all be different from each other if all components are identicalthey need not be written out individuallywe use the for statement and the array structure to indicate replication by knownfinite factor choice among two or more elements is expressed by the conditional or the case statement and by extensions of record typesrespectively and finallya repetiton by an initially unknown (and potentially infinitefactor is expressed by the while and repeat statements the corresponding data structure is the sequence (file)the simplest kind which allows the construction of types of infinite cardinality the question arises whether or not there exists data structure that corresponds in similar way to the procedure statement naturallythe most interesting and novel property of procedures in this respect is recursion values of such recursive data type would contain one or more components belonging to the same type as itselfin analogy to procedure containing one or more calls to itself like proceduresdata type definitions might be directly or indirectly recursive simple example of an object that would most appropriately be represented as recursively defined type is the arithmetic expression found in programming languages recursion is used to reflect the possibility of nestingi of using parenthesized subexpressions as operands in expressions hencelet an expression here be defined informally as followsan expression consists of termfollowed by an operatorfollowed by term (the two terms constitute the operands of the operator term is either variable -represented by an identifier -or an expression enclosed in parentheses data type whose values represent such expressions can easily be described by using the tools already available with the addition of recursiontype expression record opintegeropd opd term