Structural Recursion
From CS315
Written by Timothy Joslin
Contents |
Structural Recursion
Structural recursion refers to the implementation of recursive data types, or collection of objects that are defined recursively. A criterion for recursive data types is for each object of this type to have a reference to another object of the same type, by access of which the entire collection of sequential objects may be accessed.
Implementation in Java
In Java, this can be accomplished by having a member variable of the same type as the object itself. For example, the class List<T>:
class List<T> {
T first;
List<T> rest;
}
For List<T> object x, the current element being operated on is accessed via the member variable x.first, and the next successive element may be found by looking at x.rest.first. Indeed, this is how successive terms of this recursive data type may be accessed: via the immediate previous element, recursively.
Ultimately, the traversal of a recursively-implemented list or other structurally recursive data type is halted by a necessary attribute of all recursive data structures; that is, by the access of a predefined Base Case for the structure, after which there are no more sequential elements in the structure. In terms of the List<T> example above, one can appreciate that there are multiple ways a Base Case may be define. as with the use of a Sentinel List<T> object, or the final element in a sequence of List<T> objects having its x.rest member variable point to NULL.
Implementation in Haskell
In the functional programming language Haskell, syntax construction has oriented the language to make use of structural recursion on lists without a need for member variables of the same type as the instance itself. By use of the concept “pattern-matching”, functions on lists in Haskell make use of the recursive structure of lists, which significantly simplifies syntax. The following code sample shows an example of how Haskell utilizes pattern-matching:
contains::Int → [Int] → Bool --a type summary of contains method: arg-> arg-> output contains y [] = False contains y (x:xs) | x == y = True | otherwise = contains y xs
It is left to the reader to determine the specifics of Haskell syntax, but with regard to the structural recursion of Haskell lists, it is sufficient to understand 1.that the second argument to contains is a list of Ints, 2.that for an empty list parameter, contains returns false (specifying the base case for lists and how to operate on it for given function), and 3.how, in the second line, contains y (x:xs), (x:xs) refers to the current list parameter, with x being the current Int element in the list and xs referencing the rest of the list not including current Int x. So, it is clear how Haskell, too, supports recursive data types, and that the method for operating on them in Java is not the only way.
Advantages of Structural Recursion:
As in Haskell, implementation of lists as structurally recursive allowed for a cleaner syntax and easily understood code and algorithms. In addition to this advantage, recursive data types also provide for an arbitrary and variable number of elements to be added to the structure, unlike such fixed-size data types as an array.
