10.2 Recursive Data Structures

• A recursive data structure is one that is defined in terms of itself
• What enables recursive data structures to grow dynamically?

  Self-referential definition
• Linked lists consist of nodes, each holding data and a reference to the next node
• Match the feature with the correct data structure type:

  Self-referential definition ↔️ Recursive

  Fixed size ↔️ Non-recursive
• Recursive data structures grow or shrink in size during runtime
• Non-recursive data structures use self-referential definitions.

  False
• In the example Java code, what is the purpose of the 'next' field in the Node class?

  Reference to the next node
• Match the feature with the correct data structure:

  Sequential arrangement ↔️ Linked Lists

  Branched structure ↔️ Trees
• Linked lists and trees are common examples of recursive data structures.


  True
• What type of structure do trees have in terms of node relationships?

  Parent-child
• The recursive method to print a linked list stops when the head is null.null
• To insert a new node at the head of a linked list, you set the next pointer of the new node to the current head.
• What does the self-reference property of recursive data structures allow?

  Dynamic size
• Match the data structure with its type:

  Arrays ↔️ Non-recursive

  Linked Lists ↔️ Recursive
• Steps of memory allocation in recursive data structures:

  1️⃣ Memory is allocated during recursion

  2️⃣ Each recursive call creates new memory

  3️⃣ Memory is freed when recursion ends
• Trees have a linear structure.

  False
• Recursive data structures use their own type in their definition.

  True
• What is a key characteristic of recursive data structures regarding memory allocation?

  Memory allocation occurs during recursion
• What type of structure do trees have in recursive data structures?

  Hierarchical
• Linked lists have a sequential node arrangement, whereas trees have a hierarchical arrangement.hierarchical
• In a linked list, each node holds data and a reference to the next node in the sequence.next
• The recursive method is simpler to implement but less efficient than the iterative method.


  True
• Match the operation on a linked list with its description:

  Insertion ↔️ Adding a new node

  Deletion ↔️ Removing a node

  Traversal ↔️ Visiting each node
• A recursive data structure is defined in terms of itself, allowing for dynamic size.
• Match the characteristic with the type of data structure:

  Self-referential ↔️ Recursive

  Fixed size ↔️ Non-recursive
• Trees have a hierarchical structure with nodes branching to child nodes.


  True
• Linked lists have a linear, sequential arrangement of nodes.


  True
• What are two approaches to representing recursive data structures?

  Recursive and iterative
• What is the best use case for the recursive method?

  Educational purposes
• What type of implementation does the iterative method use?

  Loops
• What are three common operations on recursive data structures?

  Insertion, deletion, traversal
• In the Java example, where is the new node inserted in the 'insert' method?

  At the head
• What is the complexity of inserting a new node at the beginning of a linked list?

  O(1)
• What happens if the target data is not found in the linked list during deletion?

  The method returns
• What is the best-case complexity of inserting a new node into a recursive data structure?

  O(1)
• What is the complexity of traversing a linked list recursively?

  O(n)
• Why might recursive data structures be less efficient in memory usage compared to non-recursive ones?

  Recursion overhead
• Recursive data structures are defined in terms of themselves.


  True
• Recursive data structures have a fixed size.

  False
• What is the relationship between nodes in a tree structure?

  Parent-child relationship