再帰的定義

再帰的定義（Recursive Definition）

再帰的定義とは、定義される対象そのものや、それと同種の、しかしより単純な要素を用いて定義を行う手法です。「帰納的定義（Inductive Definition）」とも呼ばれます。この定義方法では、定義の中で参照される要素が適切に定義されており、無限に定義を遡る事態（無限後退）を招かないようにする必要があります。

循環定義との違い

再帰的定義が単なる循環定義と異なる点は、明確な「基本ケース（base case）」が存在することです。基本ケースは、再帰的な定義を参照することなく直接的に定義されます。基本ケース以外のより複雑なケースは、より単純で基本ケースに近い要素を用いることで定義されます。これにより、定義の連鎖は必ず基本ケースに到達し、循環に陥ることはありません。一方、循環定義にはこのような終点となる基本ケースが存在せず、ただ自身を参照し続けるため、悪循環を生み、対象を適切に定義できません。例えば、「再帰的定義とは、「再帰的定義」を参照せよ」という記述は、基本ケースがないため再帰的定義ではなく、典型的な循環定義です。

具体例：素数

再帰的定義の典型的な例として、素数の定義を挙げることができます。

1. 整数 1 は素数ではない。
2. 1より大きい正の整数がある素数であるとは、その整数自身よりも小さいすべての素数によって割り切れないことである。

この定義において、1が基本ケースとなります。素数であるか判定したいある整数Xが1より大きい場合、その判定はXよりも小さい整数が素数であるかどうかの知識に依存します。これらの小さい整数は基本ケースである1に「より近い」存在であり、この定義は有効な再帰的定義として機能します。

応用分野

再帰的定義は、その性質上、構造が再帰的な性質を持つ対象の定義に非常に適しています。特に論理学における式の構造や、コンピュータプログラミングにおけるデータ構造（リスト、木構造など）や関数の定義において頻繁に用いられます。

具体例：論理式（WFF; Well-Formed Formula）

論理学における整形式論理式（WFF）の定義も再帰的定義の良い例です。

1. 基本ケース: 命題を表す記号（例: p, q, r...）はWFFである。
2. 帰納ステップ:
AがWFFであるとき、否定を表す記号 N とAを組み合わせたもの（例: NA）もWFFである。
AとBがWFFであるとき、4種類の主要な論理演算（例えば C:ならば, A:または, K:かつ, E:同値）のいずれかを表す記号Xと、AおよびBをこの順で組み合わせたもの（例: KAB）もWFFである。

これらの規則によって構成されるものだけがWFFであると定義されます。

この定義を用いることで、ある記号列が論理的に意味のある整形式であるか否かを判定することができます。

Kpq は、WFFであるpとqが論理演算記号Kで結合されているため、WFFです。
NKpq は、WFFであるKpq全体に否定記号Nが付加されているため、WFFです。
KNpNq は、Kに続くNpとNqがそれぞれWFF（p, qがWFFであり、それにNが付加されているため）であるため、WFFです。
Npq は、否定記号Nの後ろに続いているpqが単独では定義されたWFFの形式（単一の記号または特定の結合形式）を満たさないため、WFFではありません。

このように、再帰的定義は複雑な対象や構造を、単純な要素と構成規則を用いて明確かつ厳密に定義することを可能にします。

もう一度検索