再帰的定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/15 21:00 UTC 版)
ナビゲーションに移動 検索に移動再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。
概要
循環定義との違いは、再帰的定義にはその定義を使わずに定義される基本となるケースが存在することである。その他のケースの定義は、基本のケースにより近い定義によって定義されなければならない。
例として素数の定義を示す:
- 1は素数ではない。
- 1でない正整数が素数であるとは、自身より小さいどの素数でも割り切れないことである。
整数 1 がこの場合の基本ケースである。それより大きい整数 X が素数かどうかを判定するには、X と 1 の間の全ての整数について素数かどうかを知っている必要がある。そのような整数たちは X よりも基本ケースの 1 に近いので、この定義は再帰的定義として有効である。
対照的に循環定義には基本ケースがなく、単に自身で自身を定義しているにすぎない。これが悪循環を生む。従って「再帰的定義: "再帰的定義"を参照」という記述は循環定義であって再帰的定義ではない。
再帰的定義は論理学やコンピュータプログラミングでよく見受けられる。例えば論理式 (WFF; Well-founded Formula) は次のように定義される:
- 命題を表す記号 p,q, ... はWFFである - 例えば、p は「フレッドは法律家である」、q は「メリーは音楽好きである」を意味する。
- N にWFFが付属したものはWFFである - 例えば N が否定を表すとすると、Np は「フレッドは法律家である、というのは真ではない」を意味する。
- 4種類の論理演算（C, A, K, E）のいずれかに、2つのWFFが付属したものはWFFである。 - 例えば、記号 K が「両方が真である」ことを意味するとすると、Kpq は「フレッドが法律家であり、かつメリーは音楽好きである」という意味である。
- 以上により WFF と定義されるもののみが WFF である。
このような再帰的定義を使って、ある記号列が論理式であるか否かを判定することができる。
- Kpq は、WFF である p と q が K に付属したものであるため、WFF である。
- NKpq は、WFF である Kpq が N に付属したものであるため、WFF である。
- KNpNq は、K に Np と Nq が付属しており、Np および Nq は WFF であるため、WFF である。
- Npq は WFF ではない。
再帰的定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/26 04:58 UTC 版)
次のように再帰的に定義できる。b = 0のときの例外処理がnによって違うことに注意。 hyper ( a , n , b ) = a ( n ) b = { b + 1 , if n = 0 a , if n = 1 , b = 0 0 , if n = 2 , b = 0 1 , if n ≥ 3 , b = 0 a ( n − 1 ) ( a ( n ) ( b − 1 ) ) otherwise {\displaystyle \operatorname {hyper} (a,n,b)=a^{(n)}b={\begin{cases}b+1,&{\mbox{if }}n=0\\a,&{\mbox{if }}n=1,b=0\\0,&{\mbox{if }}n=2,b=0\\1,&{\mbox{if }}n\geq 3,b=0\\a^{(n-1)}(a^{(n)}(b-1))&{\mbox{otherwise}}\end{cases}}}
※この「再帰的定義」の解説は、「ハイパー演算子」の解説の一部です。
「再帰的定義」を含む「ハイパー演算子」の記事については、「ハイパー演算子」の概要を参照ください。
再帰的定義と同じ種類の言葉
- 再帰的定義のページへのリンク
