In this lesson, you will learn how to create infinitely nested data structures in Rust by using Box to manage memory indirection.
The Problem: Infinite Size
In Rust, the compiler must know the exact size of every type at compile time. If you try to define a recursive enum like this, the compiler will complain:
enum List {
Empty,
Cons(i32, List), // Error: recursive type has infinite size
}
The compiler looks at List and thinks: "To know how big List is, I need to know the size of the Cons variant. But Cons contains another List, so I need to know the size of that first... and so on." This creates an infinite cycle that makes it impossible for Rust to allocate space on the stack.
The Solution: Indirection
To solve this, we introduce indirection. We wrap the recursive part of the enum in a Box<T>. A Box is a smart pointer that allocates its data on the heap instead of the stack. Because the heap is dynamic, the Box itself has a fixed, known size (the size of a pointer).
By using Box, we tell the compiler: "The actual List data lives somewhere else in memory, just store a pointer to it here."
enum List {
Empty,
Cons(i32, Box<List>),
}
fn main() {
let list = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Empty))));
}
Why This Works
When you use Box<List>, the size of the Cons variant changes from size(i32) + size(List) to size(i32) + size(pointer). Since a pointer size is constant, the compiler can now calculate the size of your enum perfectly. This allows you to build complex, tree-like structures like linked lists or Abstract Syntax Trees (ASTs) while maintaining Rust’s strict memory safety rules.
Key Takeaway: To define a recursive enum, you must break the infinite size cycle by wrapping the recursive variant in a Box, which shifts the nested data to the heap and provides a fixed-size pointer for the compiler.