Recursive definitionとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Recursive definitionの意味・解説 

再帰的定義

(Recursive definition から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/15 21:00 UTC 版)

ナビゲーションに移動 検索に移動

再帰的定義(Recursive Definition)は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義(Inductive Definition)がある。

概要

循環定義との違いは、再帰的定義にはその定義を使わずに定義される基本となるケースが存在することである。その他のケースの定義は、基本のケースにより近い定義によって定義されなければならない。

例として素数の定義を示す:

  • 1は素数ではない。
  • 1でない正整数が素数であるとは、自身より小さいどの素数でも割り切れないことである。

整数 1 がこの場合の基本ケースである。それより大きい整数 X が素数かどうかを判定するには、X と 1 の間の全ての整数について素数かどうかを知っている必要がある。そのような整数たちは X よりも基本ケースの 1 に近いので、この定義は再帰的定義として有効である。

対照的に循環定義には基本ケースがなく、単に自身で自身を定義しているにすぎない。これが悪循環を生む。従って「再帰的定義: "再帰的定義"を参照」という記述は循環定義であって再帰的定義ではない。

再帰的定義は論理学コンピュータプログラミングでよく見受けられる。例えば論理式 (WFF; Well-founded Formula) は次のように定義される:

  1. 命題を表す記号 p,q, ... はWFFである - 例えば、p は「フレッドは法律家である」、q は「メリーは音楽好きである」を意味する。
  2. N にWFFが付属したものはWFFである - 例えば N が否定を表すとすると、Np は「フレッドは法律家である、というのは真ではない」を意味する。
  3. 4種類の論理演算C, A, K, E)のいずれかに、2つのWFFが付属したものはWFFである。 - 例えば、記号 K が「両方が真である」ことを意味するとすると、Kpq は「フレッドが法律家であり、かつメリーは音楽好きである」という意味である。
  4. 以上により WFF と定義されるもののみが WFF である。

このような再帰的定義を使って、ある記号列が論理式であるか否かを判定することができる。

  • Kpq は、WFF である pqK に付属したものであるため、WFF である。
  • NKpq は、WFF である KpqN に付属したものであるため、WFF である。
  • KNpNq は、KNpNq が付属しており、Np および Nq は WFF であるため、WFF である。
  • Npq は WFF ではない。



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Recursive definition」の関連用語

Recursive definitionのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Recursive definitionのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの再帰的定義 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS