For the sake of simplicity a linked list structure is a recursive one, it points to itself.<\/p>\n
struct Node {
\n\u00a0int data;<\/p>\n
…<\/p>\n
…
\n\u00a0Node* next;
\n};<\/p>\n
This case is easy to follow because no matter what, you always end up with accessing a Node structure.<\/p>\n
The problem arises when you have\u00a0recursive data-structures and terminals. I treat a terminal as a data structure which stops the recursion of the recursive data-structure. Unlike the above linked list structure, which stops when the ‘next’ pointer is NULL, the ‘next’ in the complex data-structure might point to either itself or a terminal.<\/p>\n
\u00a0struct TerminalNode {<\/p>\n
\u00a0int data;<\/p>\n
};<\/p>\n
\u00a0struct Node {<\/p>\n
\u00a0int data;<\/p>\n
\u00a0Node* next;<\/p>\n
};<\/p>\n
Now you might find yourselves asking why would one make the ‘next’ point to a TerminalNode, but that’s a common data-structure layout. For example, an expression tree can represent arithmetic operations in a recursive way, but the values are<\/em> the terminals – Add(5, Sub(3, 2)).<\/p>\n In a structured layout, it looks something like this (where children is an array of pointers to ‘next’ nodes):<\/p>\n 0: ExpressionNode: (type) Add, (children) 1, 2<\/p>\n 1: ExpressionNode: (type) Value 5, (children) NULL<\/p>\n 2: ExpressionNode: (type) Sub, (children) 3, 4<\/p>\n 3: ExpressionNode: (type) Value 3, (children) NULL<\/p>\n 4: ExpressionNode: (type) Value 2, (children) NULL<\/p>\n So you can see that in this case an ExpressionNode of ‘Value’ type is a TerminalNode whereas the ExpressionNode is a recursive one.<\/p>\n