再帰的定義
循環定義との違いは、再帰的定義にはその定義を使わずに定義される基本となるケースが存在することである。その他のケースの定義は、基本のケースにより近い定義によって定義されなければならない。
例として素数の定義を示す:
1は素数ではない。
1でない正整数が素数であるとは、自身より小さいどの素数でも割り切れないことである。
整数 1 がこの場合の基本ケースである。それより大きい整数 X が素数かどうかを判定するには、X と 1 の間の全ての整数について素数かどうかを知っている必要がある。そのような整数たちは X よりも基本ケースの 1 に近いので、この定義は再帰的定義として有効である。
対照的に循環定義には基本ケースがなく、単に自身で自身を定義しているにすぎない。これが悪循環を生む。従って「再帰的定義: "再帰的定義"を参照」という記述は循環定義であって再帰的定義ではない。
再帰的定義は論理学やコンピュータプログラミングでよく見受けられる。例えば論理式 (WFF; Well-founded Formula) は次のように定義される:
命題を表す記号 p,q, ...