Recursive Enum Types

2

Your enum is still recursive

pub enum BTree<T> {
    Node(T),
    Branch(Box<BTree<T>>, Box<BTree<T>>)
}

Boxing the T isn't necessary here, but you need to box all recursive things.

The problem with recursive enums is that they don't have a well-defined size. Something like Branch(Branch(Branch(......))) can go on forever, and the whole thing needs to be stored in statically allocated memory -- impossible for something which is possibly infinitely-sized.

Putting a Box<> around the recursive bit means that a single Btree<T> is either a node or a branch, containing pointers to other btrees. Thus, the stack representation is bounded by the size of a node or two pointers.

Recursive enums are supported as long as you use indirection.

4 Likes