再帰データ型
型システムは名前的型システムと構造的型システムに分かれる。名前的型システムは Java を始め、多くのプログラミング言語で採用されていて、型に名前を付け、Java なら extends で何を継承しているか型の名前を使って記載する方法で、それを見れば再帰型であっても部分型関係(継承しているかどうか)は簡単に分かる。構造的型システムは、型の名前で判定するのではなく、型の構造で部分型関係にあるかどうか(関数の引数に渡せるかどうかなど)を判定する。以下、ここで述べるのは、構造的型システムでの再帰型の理論である。
型理論では、再帰型の一般形はμ型構築子を用いて μα.T で表される。ここで型変数 α は型そのものであると共に、型 T の中にも現われる可能性がある。部分型関係かどうかは S <: T と記載する。名前的型システムの Java ならば S extends T または S implements T (ただし親クラスを Object までたどる)であることを意味する。