Ownership in Recursive Structures

A recursive data structure (such as a binary tree, abstract syntax tree, trie, or DOM hierarchy) is a type whose definition contains nested instances of itself. In Rust, designing recursive structures requires choosing an indirection and ownership model that matches whether nodes have a single parent, shared parents, or parent back-pointers.

Why Direct Recursion Fails (`error[E0072]: recursive type has infinite size`):
  struct BadNode { val: i32, child: Option<BadNode> }  --> Infinite size!

Three Indirection Models for Recursive Structures in Rust:
  1. Unique Tree Ownership:    `Option<Box<Node>>`  (Fastest for pure trees/ASTs)
  2. Shared DAG / Parent Refs: `Rc<RefCell<Node>>` + `Weak<RefCell<Node>>` (For parent links)
  3. Contiguous Index Tree:    `NodeId(u32)` into `Vec<Node>` (Best cache locality & zero Box overhead)

Comparing Ownership Models for Recursive Trees and DAGs

1. Unique Ownership in an Expression AST (Box<Expr>)

When a recursive type is a strict tree where children never need pointers back to their parent (such as an Abstract Syntax Tree or JSON value), Box<T> (or Vec<T> for n-ary children) is simple, thread-safe (Send + Sync), and mutates via ordinary &mut:

#[derive(Debug, PartialEq, Eq)]
pub enum Expr {
    Literal(i64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

impl Expr {
    pub fn eval(&self) -> i64 {
        match self {
            Expr::Literal(n) => *n,
            Expr::Add(l, r) => l.eval() + r.eval(),
            Expr::Mul(l, r) => l.eval() * r.eval(),
        }
    }
}

2. Parent Back-Pointers Without Reference Cycles (Rc + Weak)

When each tree node must hold a reference to its parent (for example, walking up a UI widget tree or XML DOM), using Rc for both children and parent creates a reference cycle ($A \leftrightarrow B$) whose reference count never reaches 0, leaking memory!

To prevent cycles:

• Parent owns children via strong Rc<RefCell<DomNode>>.
• Child references parent via non-owning Weak<RefCell<DomNode>> (which does not prevent the parent from being dropped and is accessed safely via .upgrade() -> Option<Rc<...>>):

use std::cell::RefCell;
use std::rc::{Rc, Weak};

pub struct DomNode {
    pub tag: &'static str,
    pub parent: RefCell<Weak<DomNode>>,
    pub children: RefCell<Vec<Rc<DomNode>>>,
}

impl DomNode {
    pub fn new(tag: &'static str) -> Rc<Self> {
        Rc::new(Self {
            tag,
            parent: RefCell::new(Weak::new()),
            children: RefCell::new(Vec::new()),
        })
    }

    pub fn append_child(parent: &Rc<Self>, child: Rc<Self>) {
        // Set child's non-owning `Weak` parent pointer:
        *child.parent.borrow_mut() = Rc::downgrade(parent);
        parent.children.borrow_mut().push(child);
    }

    pub fn parent_tag(&self) -> Option<&'static str> {
        self.parent.borrow().upgrade().map(|p| p.tag)
    }
}

fn main() {
    let root = DomNode::new("body");
    let paragraph = DomNode::new("p");

    DomNode::append_child(&root, Rc::clone(&paragraph));

    assert_eq!(paragraph.parent_tag(), Some("body"));
    assert_eq!(Rc::strong_count(&root), 1);
    assert_eq!(Rc::weak_count(&root), 1);

    println!(
        "Child <{}> has parent <{:?}> (root strong_count={})",
        paragraph.tag,
        paragraph.parent_tag(),
        Rc::strong_count(&root)
    );
}

Child <p> has parent <Some("body")> (root strong_count=1)