Recursive Data Structures

In this lesson, you will learn how to design data structures that contain themselves, effectively bypassing the constraints of fixed-size stack memory.

The Problem of Infinite Size

In Rust, the compiler must know exactly how much memory to allocate for a struct at compile time. If you define a struct Node { value: i32, next: Node }, the compiler faces a logical paradox: to calculate the size of Node, it needs the size of Node, which includes another Node, and so on. This creates an infinitely large struct, which is impossible to place on the stack.

Breaking the Cycle with Indirection

To create recursive structures like linked lists or trees, we must introduce indirection. We need to store the recursive part of our structure on the heap rather than the stack. Since heap-allocated memory is accessed via a pointer, the size of the pointer itself is known at compile time (it’s just a memory address), resolving the infinite size issue.

We achieve this using Box<T>, which acts as a "smart pointer" that moves data from the stack to the heap:

struct Node {
    value: i32,
    // We wrap the recursive part in a Box
    next: Option<Box<Node>>,
}

fn main() {
    let list = Node {
        value: 1,
        next: Some(Box::new(Node {
            value: 2,
            next: None,
        })),
    };
}

Navigating Ownership

When you use a Box<Node>, you are asserting full ownership of the next node. Because the Box owns the data it points to, the standard ownership rules apply: when the Box is dropped, the memory on the heap is automatically deallocated.

However, this strict ownership creates a "tree-like" hierarchy. Each node has exactly one parent that owns it. If you try to create a graph where multiple nodes point to the same child, you will violate the single-owner rule. Recursive structures like trees work perfectly with Box because they follow a strict parent-child ownership chain, but cycles (like in a graph) require more advanced tools that we haven't covered yet. For now, focus on the power of Box to provide the indirection necessary for recursive definitions.

Key Takeaway: To define a recursive structure in Rust, you must use a pointer type like Box to allocate the recursive portion on the heap, providing the compiler with a fixed size for the structure on the stack.