Recursive Data Structures

Read this page. In the previous unit of our course we studied recursive algorithms. Recursion is a concept that also applies to data. Here we look at recursive data structures - lists, trees, and sets. A list is a structure that consists of elements linked together. If an element is linked to more than one element, the structure is a tree. If each element is linked to two (sub) elements, it is called a binary tree. Trees can be implemented using lists, as shown in the resource for this unit. Several examples of the wide applicability of lists are presented. A link points to all the remaining links, i.e. the rest of the list or the rest of the tree; thus, a link points to a list or to a tree - this is data recursion.

The efficiency of the programming process includes both running time and size of data. This page discusses the latter for recursive lists and trees.

Lastly, why read the last section on sets? Sets are another recursive data structure and the last section 2.7.6, indicates their connection with trees, namely, a set data type can be implemented in several different ways using a list or a tree data type. Thus, the programming process includes implementation decisions, in addition, to design or algorithm decisions. Each of these types of decisions is constrained by the features of the programming language used. The decision choices, such as which data structure to use, will impact efficiency and effectiveness of the program's satisfaction of the program's requirements.

Note: You will notice an unusual use of C++ here. What the author is doing is showing how to pass a fixed-value data-structure as a calling argument.

5. Isomorphic data structures

When we have what ought to be an elegant algorithm, but the interface between the algorithm and the data structure ends up being as complicated as the rest of the algorithm put together, we can always ask ourselves, "What data structure would make this algorithm stupidly simple?"

The answer can often be found by imagining a data structure that looks like the algorithm's basic form. If we follow that heuristic, our data structure would be recursive, rather than ‘flat.' Since we do all kinds of work sorting out which squares form the four regions of a bigger square, our data structure would describe a square as being composed of four region squares.

Such a data structure already exists, it's called a quadtree. Squares are represented as four regions, each of which is a smaller square or a cell. A simple implementation is a "Plain Old JavaScript Object" (or "POJO") with properties for each of the regions. If the property contains a string, it's cell. If it contains another POJO, it's a quadtree.

A square that looks like this:

⚪️⚫️⚪️⚪️
 ⚪️⚪️⚫️⚪️
 ⚫️⚫️⚫️⚪️
 ⚪️⚪️⚪️⚪️

Is composed of four regions, the ul ("upper left"), ur ("upper right"),  lr ("lower right"), and ll ("lower left"), something like this:

ul | ur
 ---+---
 ll | lr

Thus, for example, the ul is:

⚪️⚫️
 ⚪️⚪️

And the ur is:

⚪️⚪️
 ⚫️⚪️

And so forth. Each of those regions is itself composed of four regions. Thus, the ul of the ul is  ⚪️, and the ur of the  ul is ⚫️.

The quadtree could be expressed in JavaScript like this:

const quadTree = {
  ul: { ul: '⚪️', ur: '⚫️', lr: '⚪️', ll: '⚪️' },
  ur: { ul: '⚪️', ur: '⚪️', lr: '⚪️', ll: '⚫️' },
  lr: { ul: '⚫️', ur: '⚪️', lr: '⚪️', ll: '⚪️' },
  ll: { ul: '⚫️', ur: '⚫️', lr: '⚪️', ll: '⚪️' }
};

Now to our algorithm. Rotating a quadtree is simpler than rotating an array of arrays. First, our test for indivisibility is now whether something is a string or not: 

const isString = (something) => typeof something === 'string';

The value of an indivisible cell remain the same, itself.

Our divide function is simple: quadtrees are already divided in the manner we require, we just have to turn them into an array of regions:

const quadTreeToRegions = (qt) =>
  [qt.ul, qt.ur, qt.lr, qt.ll];

And finally, our combine function reassembles the rotated regions into a POJO, rotating them in the process:

const regionsToRotatedQuadTree = ([ur, lr, ll, ul]) =>
  ({ ul, ur, lr, ll });

And here's our function for rotating a quadtree:

const rotateQuadTree = multirec({
  indivisible : isString,
  value : itself,
  divide: quadTreeToRegions,
  combine: regionsToRotatedQuadTree
});

Let's put it to the test:

rotateQuadTree(quadTree)
  //=>
    ({
       ul: { ll: "⚪️", lr: "⚫️", ul: "⚪️", ur: "⚫️" },
       ur: { ll: "⚪️", lr: "⚫️", ul: "⚪️", ur: "⚪️" },
       lr: { ll: "⚪️", lr: "⚪️", ul: "⚫️", ur: "⚪️" },
       ll: { ll: "⚪️", lr: "⚪️", ul: "⚪️", ur: "⚫️" }
     })

If we reassemble the square by hand, it's what we expect:

⚪️⚫️⚪️⚪️
 ⚪️⚫️⚪️⚫️
 ⚪️⚫️⚫️⚪️
 ⚪️⚪️⚪️⚪️

Now we can be serious about the word "Isomorphic". Isomorphic means, fundamentally, "having the same shape". Obviously, a quadtree doesn't look anything like the code in rotateQuadTree or  multirec. So how can a quadtree "look like" an algorithm? The answer is that the quadtree's data structure looks very much like the way rotateQuadTree behaves at run time.

More precisely, the elements of the quadtree and the relationships between them can be put into a one-to-one correspondance with the call graph of rotateQuadTree when acting on that quadtree.