Why are recursive struct types illegal in Rust?

Data inside structs and enums (and tuples) is stored directly inline inside the memory of the struct value. Given a struct like

struct Recursive {
    x: u8,
    y: Option<Recursive>

let’s compute the size: size_of::<Recursive>(). Clearly it has 1 byte from the x field, and then the Option has size 1 (for the discriminant) + size_of::<Recursive>() (for the contained data), so, in summary, the size is the sum:

size_of::<Recursive>() == 2 + size_of::<Recursive>()

That is, the size would have to be infinite.

Another way to look at it is just expanding Recursive repeatedly (as tuples, for clarity):

Recursive ==
(u8, Option<Recursive>) ==
(u8, Option<(u8, Option<Recursive>)>) ==
(u8, Option<(u8, Option<(u8, Option<Recursive>)>)>) ==

and all of this is stored inline in a single chunk of memory.

A Box<T> is a pointer, i.e. it has a fixed size, so (u8, Option<Box<Recursive>>) is 1 + 8 bytes. (One way to regard Box<T> is that it’s a normal T with the guarantee that it has a fixed size.)

Leave a Comment