Recursive Types

A recursive type is a struct or enum whose definition contains a value of its own type, either directly (such as a linked list node or binary tree) or mutually through another type (such as Expr containing Block and Block containing Expr). Because the Rust compiler must compute the exact byte size of every Sized type at compile time, direct by-value recursion is rejected unless broken by pointer indirection (Box<T>, Rc<T>, Arc<T>, &T, or Vec<T>).

Why Direct Recursion Fails (E0072)

To compute the size of enum List { Cons(i32, List), Nil }, the compiler expands the variant sizes recursively:

$$\text{size}(\text{List}) = 4 + \text{size}(\text{List}) = 4 + 4 + \text{size}(\text{List}) = \infty$$

Because the expansion never terminates, rustc rejects the definition with error E0072 and suggests wrapping the recursive field in Box<T>:

// ❌ does not compile
enum List {
    Cons(i32, List),
    Nil,
}

fn main() {}

error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:2:1
  |
2 | enum List {
  | ^^^^^^^^^
3 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
3 |     Cons(i32, Box<List>),
  |               ++++    +

Breaking the Cycle with Box<T>

Replacing List with Box<List> gives the recursive field a fixed compile-time size of one pointer word (8 bytes on 64-bit targets). Furthermore, because Box<List> contains a non-null pointer, List benefits from niche optimization: Nil is represented as the null niche (0x0), so the entire List enum occupies 16 bytes (i32 + 4 bytes padding + 8-byte pointer).

Direct Recursion (Infinite Size — Rejected):
+---------+-------------------------------+
| i32 (4) | List                          |
|         | +---------+-----------------+ |
|         | | i32 (4) | List (infinite) | |
|         | +---------+-----------------+ |
+---------+-------------------------------+

Boxed Indirection (Finite 16-Byte Stack Size):
+---------+---------+-------------------+        +---------+---------+-------------------+
| i32: 1  | pad (4) | next: Box<List> --+------> | i32: 2  | pad (4) | next: Nil (0x0)   |
+---------+---------+-------------------+        +---------+---------+-------------------+

#[derive(Debug)]
enum List {
    Cons(i32, Box<List>),
    Nil,
}

impl List {
    fn sum(&self) -> i32 {
        match self {
            List::Cons(head, tail) => head + tail.sum(),
            List::Nil => 0,
        }
    }
}

fn main() {
    let list = List::Cons(
        10,
        Box::new(List::Cons(20, Box::new(List::Cons(30, Box::new(List::Nil))))),
    );

    println!("size of List: {} bytes", size_of::<List>());
    println!("sum of list:  {}", list.sum());
}

size of List: 16 bytes
sum of list:  60

Recursive Structs with Optional Children (Binary Tree)

In a struct-based recursive data structure such as a binary search tree node, every leaf must terminate the recursion. Using Option<Box<Node<T>>> for child pointers represents absent children as None (0x0 via null-pointer niche optimization) and present children as Some(Box<Node<T>>) in a single 8-byte word per child pointer.

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

impl<T: Ord> TreeNode<T> {
    fn new(value: T) -> Self {
        Self {
            value,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, new_val: T) {
        let target = if new_val < self.value {
            &mut self.left
        } else {
            &mut self.right
        };
        match target {
            Some(child) => child.insert(new_val),
            None => *target = Some(Box::new(TreeNode::new(new_val))),
        }
    }

    fn inorder(&self, out: &mut Vec<&T>) {
        if let Some(left) = &self.left {
            left.inorder(out);
        }
        out.push(&self.value);
        if let Some(right) = &self.right {
            right.inorder(out);
        }
    }
}

fn main() {
    let mut root = TreeNode::new(50);
    for v in [30, 70, 20, 40, 60, 80] {
        root.insert(v);
    }

    let mut sorted = Vec::new();
    root.inorder(&mut sorted);
    println!("TreeNode<i32> size: {} bytes", size_of::<TreeNode<i32>>());
    println!("inorder traversal:  {:?}", sorted);
}

TreeNode<i32> size: 24 bytes
inorder traversal:  [20, 30, 40, 50, 60, 70, 80]