Borrow Checking in Recursive Structures

In this lesson, you will learn how to navigate the "ownership paradox" that arises when building recursive data structures like linked lists or trees in Rust.

The Recursive Ownership Problem

In many languages, a node in a tree can simply hold a pointer to its parent or siblings. However, Rust’s borrow checker enforces a strict rule: an owner must be unique. If a parent owns its child, and that child tries to own its parent, you create a cycle of ownership that prevents memory from ever being dropped. Even if you don't create a cycle, the borrow checker struggles to track how long a nested structure lives if every node is just a reference to another.

Solving Depth with Indirection

To manage ownership depth in recursive structures, we move away from nesting values directly. If you try to define a struct like this:

struct Node {
    value: i32,
    next: Node, // Error: Recursive types must have a known size
}

The compiler rejects this because it doesn't know how much memory to allocate—a node containing a node could be infinitely large! We solve this using indirection, typically Box<T>. A Box puts the data on the heap and gives the struct a fixed size (the size of a pointer).

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

Borrowing Through the Depth

Once you have this heap-allocated depth, the borrow checker still cares about how you access it. If you want to traverse this list, you use references:

fn print_nodes(node: &Node) {
    println!("{}", node.value);
    if let Some(next_node) = &node.next {
        print_nodes(next_node); // Recursion via references
    }
}

Because next_node is a reference, the borrow checker ensures that the entire chain remains valid while you are reading it. It prevents you from accidentally dropping or moving a middle node while you are currently looking at the tail. By using Box for ownership and & for traversing, you satisfy the compiler's need for strict, non-ambiguous memory management without running into infinite size errors.

Key Takeaway: To handle recursive structures, use Box to provide fixed-size heap indirection for ownership and use immutable references to traverse depths without violating borrowing rules.