A recursive data structure is an object or class that contains an abstraction of itself.
In mathematical terms, we say that the object is "isomorphic" to itself. The basic embodiment of a recursive data structure is the Composite Design pattern 1 . Recursive data structures enable us to represent repetitive abstract patterns. In such, they enable us to generate or represent complexity from simplicity.
Characteristics of a recursive data structure:
- Abstract representation : Since the actual total structure of the data is not known until run-time, the data must be represented by an abstraction, such as an abstract class or interface.
- Base case(s) : These represent the "end" of the pattern. They are the termination point(s) of the data structure.
- Inductive case(s) : These represent the on-going, "interior" portion of the repetitive pattern. They embody the ability to represent the data structure as a a simple connection between abstractly equivalent entities.
Recursive data structures are arguably the most important data structure in computer science as they are able to represent arbitrarily complex data. Indeed, if one looks across all the sciences, one sees that one of the fundamental modeling tools used is to attempt to
- 瀏覽次數：1209
