ReferringToRecursiveStructureMakesRecursive

DRAFT

Correction

Here is what's right.

class List {
  Node head;
}

class Node {
  Node next;
}

Class List is not part of a recursive data structure. It only refers to such a structure (via the head field).

In the class diagram (i.e., graph) for the above example, class List is not part of a cycle. Class Node, however, is part of a cycle (more specifically, has a self-loop). Thus class Node is part of a recursive data structure, a structure where nodes directly refer to nodes.

Origin of Misconception

The above example shows where that misconception might appear. Students believe that class List is “indirectly recursive”. However, class List is not recursive at all. Class Node is recursive.