反復的（再帰的）帰納型

帰納的型の真の力は、コンストラクタが定義中の型自身の値を受け取れることだ。これは単純な直和型・直積型から、システムプログラミングのあらゆる場面に登場する豊かな再帰構造 — リスト、木、文法 — への飛躍だ。

反復的（または再帰的）帰納型とは、少なくとも一つのコンストラクタに型自身と同じ型のフィールドを持つ帰納的型だ。帰納ステップを繰り返し適用することで任意の深さの値を構築できるため、「反復的」と呼ばれる。

間接参照が必要な理由

帰納的型で説明しているように、Rustはすべての型のサイズをコンパイル時に計算する。裸の再帰フィールドは無限に大きい型を要求する。

// error: recursive type `List` has infinite size
enum List<T> {
    Nil,
    Cons(T, List<T>), // List の中に List があり、その中にまた…
}

修正方法は固定サイズの間接参照だ。Box<T> は部分値をヒープに格納し、その場所にポインタを保持する。ポインタは指し示す対象に関係なく常にポインタサイズなので、循環が断ち切られる。

enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

単方向連結リスト

List<T> が典型例だ。コンストラクタは二つある。

Nil — 空のリスト（基底ケース、再帰フィールドなし）
Cons(T, Box<List<T>>) — 短いリストの先頭に要素を追加したもの（帰納ステップ）

リストの構築と走査は次のようになる。

enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

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

fn main() {
    let list = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Cons(3, Box::new(List::Nil))))));
    println!("{}", sum(&list)); // 6
}

Nil のアームが基底ケース。Cons のアームは head を取り出して tail に再帰する。tail は Box<List<T>> だが、Rustは match 内で Box を自動的に参照外しするため、*tail ではなく tail と書ける。

二分木

二分木には分岐がある。各ノードは値と二つの部分木を持つか、データのない葉かのどちらかだ。

enum Tree<T> {
    Leaf,
    Node { val: T, left: Box<Tree<T>>, right: Box<Tree<T>> },
}

深さを求める関数も同じ構造的再帰パターンを使う。

fn depth<T>(tree: &Tree<T>) -> usize {
    match tree {
        Tree::Leaf => 0,
        Tree::Node { left, right, .. } => 1 + depth(left).max(depth(right)),
    }
}

Tree::Leaf が基底ケース、Tree::Node が帰納ステップだ。各再帰呼び出しは元より厳密に小さい部分木を受け取るため、関数は停止する。

構造的再帰が常に停止する理由

再帰的帰納型のすべての値は、より小さい値から構築される。Cons(head, tail) は既存の tail から構築され、Node { left, right, .. } は既存の left と right から構築される。構造的再帰はこの構築を逆向きに辿る。各再帰呼び出しは基底ケースに一段階近い部分値を受け取る。有限のRustプログラムには無限の値が存在しないため、連鎖は必ず基底ケースに到達する。

これは数学的帰納法と同じ保証であり、これらの型が帰納的と呼ばれる理由だ。

その他の間接参照の選択肢

Box<T> は部分値の唯一の所有権を与える。再帰型には他に二つのポインタ型が有用な場合がある。

Rc<T> — 同一スレッド上での参照カウントによる共有所有権（後のチェックポイントで扱う）
Arc<T> — スレッド間でのアトミックな参照カウントによる共有所有権（後のチェックポイントで扱う）

どちらも Box<T> と同様に無限サイズの循環を断ち切る。どれを選ぶかは、複数の親でノードを共有する必要があるかによる — 単純な木やリストには Box<T> が正しいデフォルトだ。

対比：フラットな再帰構造としての `Vec<T>`

Vec<T> は実装上は再帰的だが（ヒープ上のバッファを所有する）、型定義の意味では再帰バリアントではない。Vec<i32> は保持する整数の数に関係なく同じ型を持つ。再帰はアロケータ内部に隠されており、型のコンストラクタにエンコードされていない。

List<T> のような再帰的帰納型は長さを型の構造にエンコードする。三要素のリストは型の形状が Cons(_, Box<Cons(_, Box<Cons(_, Box<Nil>)>)>) だ。Vec<i32> は常にただの Vec<i32> だ。どちらも有用であり、違いを理解することでどちらのパターンを選ぶべきかがわかる。

まとめ

反復的帰納型は、同じ型のフィールドを持つコンストラクタを少なくとも一つ持つ。
Rustはすべての型がコンパイル時に既知の有限サイズを持つ必要があるため、再帰フィールドを固定サイズの間接参照（標準的な選択は Box<T>）の背後に置くことを要求する。
再帰的帰納型に対する構造的再帰は停止する。各再帰呼び出しは厳密に小さい部分値に対して動作し、基底ケースは再帰フィールドを持たないためだ。
Rc<T> と Arc<T> は、部分値の共有所有権が必要なときに Box<T> の代替となる。

間接参照が必要な理由

単方向連結リスト

二分木

構造的再帰が常に停止する理由

その他の間接参照の選択肢

対比：フラットな再帰構造としての Vec<T>

まとめ

対比：フラットな再帰構造としての `Vec<T>`