A recursive data structure is a data structure that is partially composed of smaller or simpler instances of the same data structure.

For example, linked lists and binary trees can be viewed as recursive data structures.

A list is a recursive data structure because a list can be defined as either (1) an empty list or (2) a node followed by a list.

A binary tree is typically defined as (1) an empty tree or (2) a node pointing to two binary trees, one its left child and the other one its right child.

A stack is a recursive data structure, so it's:

• a stack is either empty or
• it consists of a top and the rest which is a stack by itself;