Почему рекурсивные структуры данных запрещены в Rust и как их создать правильно?

Почему Rust запрещает прямую рекурсию?

Проблема в том, что Rust должен знать точный размер каждого типа на этапе компиляции. Когда вы пишете next: Node, компилятор пытается вычислить размер Node:

size_of(Node) = size_of(i32) + size_of(Node)  // бесконечная рекурсия!

Размер становится бесконечным, потому что каждый Node содержит ещё один Node. В C вы используете указатель (Node*), который всегда имеет фиксированный размер (8 байт на 64-битной системе), поэтому рекурсия безопасна. В Rust указатели тоже имеют фиксированный размер, но нужно явно указать, что мы используем кучу (heap), а не стек (stack).

Решение: Box (умный указатель на кучу)

Box<T> — это указатель на данные в куче. Его размер всегда равен размеру указателя (8 байт), независимо от того, какой тип T внутри. Таким образом рекурсия становится конечной:

struct Node {
    value: i32,
    next: Box<Node>, // Box занимает 8 байт, рекурсия конечна
}

Теперь size_of(Node) = size_of(i32) + size_of(Box<Node>) = 4 + 8 = 12 байт. Компилятор счастлив.

Практический пример: односвязный список

struct Node {
    value: i32,
    next: Option<Box<Node>>, // Option позволяет иметь пустой конец списка
}

impl Node {
    fn new(value: i32) -> Self {
        Node { value, next: None }
    }

    fn append(&mut self, value: i32) {
        match self.next {
            Some(ref mut next_node) => next_node.append(value),
            None => self.next = Some(Box::new(Node::new(value))),
        }
    }
}

fn main() {
    let mut head = Node::new(1);
    head.append(2);
    head.append(3);
    // head: Node(1) -> Node(2) -> Node(3) -> None
}

Другие рекурсивные структуры

Тот же принцип работает для деревьев, графов и любых рекурсивных типов:

// Бинарное дерево
struct TreeNode {
    value: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

// Рекурсивный enum (списки часто делают так)
enum List {
    Cons(i32, Box<List>),
    Nil,
}

Почему не Rc или Arc?

Rc<T> (счетчик ссылок) тоже работает для рекурсии, но он используется для разделяемого владения. Для простых односвязных списков Box — правильный выбор, так как он обеспечивает единственного владельца и минимальные накладные расходы.

Важно: Rust не запрещает рекурсивные типы — он требует, чтобы рекурсия была «разорвана» через указатель фиксированного размера. Box, Rc, Arc и сырые указатели (*const T) — все они имеют известный размер и позволяют создавать рекурсивные структуры.

struct Node {
    value: i32,
    next: Option<usize>, // индекс следующего узла в векторе
}

struct LinkedList {
    nodes: Vec<Node>,
}

impl LinkedList {
    fn new(value: i32) -> Self {
        LinkedList {
            nodes: vec![Node { value, next: None }],
        }
    }

    fn append(&mut self, value: i32) {
        let new_index = self.nodes.len();
        // Находим последний узел и обновляем его next
        if let Some(last) = self.nodes.iter_mut().last() {
            last.next = Some(new_index);
        }
        self.nodes.push(Node { value, next: None });
    }
}