Topic: recursive data structures

topics > computer science > data > Group: data structures

hierarchical structures
list processing
pointer rotation
pointers to data
ref_any or Object data type
representing a relationship
safe use of pointers
self reference


Potential infinite structures, such as trees and lists, can be compactly described by recursion. For instance a tree is recursively defined as a value or a pair of trees. When implemented, a recursive data structure contains pointers to repetitions of the data structure. Recursive procedures are used to process recursive data structures. The simplest recursive structure, embedded lists, is often used as a universal data type. For instance LISP uses two element lists. Jackson claims that recursion is not needed for data processing. (cbb 5/80)

General use of pointers makes a program hard to maintain. Francis recommends restricting programs to hierarchical data structures. (cbb 1/90)

Subtopic: recursive definition up

Quote: define stack as either empty or a top element with a bottom stack [»deapAM2_1984]

Subtopic: recursive data structure up

Quote: use reference types to link records into structural networks of any desired complexity [»wirtN6_1966]
Quote: a plex is an interconnect set of n-component elements; represents arbitrarily complex information from any source; e.g., a line has a type, a name, and its two end points
Quote: a data structure is all fields reachable from some aggregate [»hallJC5_1974]
QuoteRef: dahlOJ_1972 ;;145 recursive data structures are ones with pointers

Subtopic: data structure vs. program up

Quote: can data structures be like programs with a hierarchical, nested sequential, static structure [»wileDS11_1973]
Quote: simplify recursive data structures by a single parent for each node; use a move operation to transfer pointers [»franRS4_1983]

Subtopic: compress up

Quote: compress pointer structures by replacing pointers with computed offsets; e.g., implicit heap [»chilTM12_2000]

Subtopic: examples up

QuoteRef: dahlOJ_1972 ;;145 recursive data structures by bit streams (assumed binary list, one for sublist and 0 for terminal) highly dense for external storage
QuoteRef: gullWE2_1979 ;;79 "In this paper we consider an extension of the data structure capability of APL that allows heterogeneous collections of data objects in a recursively defined data structure.
QuoteRef: hoarCA10_1973 ;;7 recursive data structures eg type list = (unit (identifier) cons (list) or = cases p of (predicate -> 0 | predicate -> whatever)
QuoteRef: hoarCA10_1973 ;;17 generation of recursive data structures
QuoteRef: kiebRB9_1973 ;;2.4 "...the name of a type cannot appear as a field of its own declaration eg L:((->r),L)
QuoteRef: rovnPD_1968 ;;581 any part of triple can be a triple

Subtopic: problems with recursive data structures up

Quote: pointer-linked data structures are error prone due to unconstrained use of pointers [»franRS4_1983]
Quote: use contiguous, pointer-free storage for in-memory data structures; random access is expensive, like disks [»zobeJ11_2005]
Quote: ESP supports record, union, and array data types; ESP does not support recursive data types; no model checker, more expensive to communicate [»kumaS6_2002]
Quote: Jackson avoids recursive data structures because they occur rarely in data processing

Related Topics up

Topic: hierarchical structures (46 items)
Topic: list processing (15 items)
Topic: pointer rotation (11 items)
Topic: pointers to data (55 items)
Topic: recursion (16 items)
Topic: ref_any or Object data type (9 items)
Topic: representing a relationship (28 items)
Topic: safe use of pointers (102 items)
Topic: self reference
(27 items)

Updated barberCB 12/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.