Summary
Recursive data types are data types which are defined in terms of themselves, such as lists and trees. There is a single access path to each component in a recursive data structure.
Generalized recursive data structures may include multiple access paths to some parts of the data structure. Two way lists, threaded trees and circular lists are generalized recursive data types. The extra access paths in a generalized recursive data structure are uniquely determined by the type of the structure and the main paths through the structure.
An extension to Pascal in which generalized recursive data structures may be defined is described.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Böhm, C., Jacopini, G.: Flow diagrams, turing machines and languages with only two formation rules. Comm. A.C.M. 9, 366–371 (1966)
Hoare, C.A.R.: Notes on data structures. In: APIC studies in data processing, No. 8: Structured programming, pp. 83–174. London and New York: Academic Press 1972
Hoare, C.A.R.: Recursive data structures. International J. of Comp. and Info. Sciences 4, 105–132 (1975)
Jensen, K., Wirth, N.: Pascal user manual and report, 2nd ed. New York-Heidelberg-Berlin: Springer-Verlag 1974
Shneiderman, B., Scheuermann, P.: Structured data structures. Comm. A.C.M. 17, 566–574 (Oct. 1974)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Burton, W. Generalized recursive data structures. Acta Informatica 12, 95–108 (1979). https://doi.org/10.1007/BF00266046
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00266046