DRAFT
ReferringToRecursiveStructureMakesRecursive
Incorrect
A class referring to a recursive data structure is (indirectly) part of that recursion as well
Correct
CorrectionHere is what's right.
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.