再帰
ページは半保護されています

ドロステ効果として知られる視覚的な再帰。この画像の女性は物体を手に持ち、その物体には同じ物体を持つ彼女の小さな像が含まれており、その物体にはさらに同じ物体を持つ彼女の小さな像が含まれており、これが繰り返される。1904年、ヤン・ミセットがデザインしたドロステのココア缶。

再帰は、概念やプロセスの定義が、それ自体のより単純な、あるいは以前のバージョンに依存する場合に発生します。[ 1 ]再帰は、言語学から論理学に至るまで、様々な分野で用いられています。再帰の最も一般的な応用分野は数学とコンピュータサイエンスであり、定義中の関数がそれ自体の定義内に適用されます。これは一見すると無限の数のインスタンス（関数値）を定義しているように見えますが、多くの場合、無限ループや参照の無限連鎖が発生しないような方法で行われます。

再帰的なプロセスは再帰的です。ビデオフィードバックは、無限遠鏡のように再帰的な画像を表示します。

正式な定義

ウロボロス、蛇または竜が自分の尾を食べる様子を描いた古代のシンボル

数学とコンピュータ サイエンスでは、オブジェクトまたはメソッドのクラスは、次の 2 つのプロパティによって定義できる場合に再帰的な動作を示します。

  • 単純なベースケース（または複数のケース）—答えを生成するために再帰を使用しない終了シナリオ
  • 再帰ステップ— 連続するすべてのケースを基本ケースに近づける一連のルール。

例えば、以下はある人の祖先の再帰的な定義です。人の祖先は次のいずれかです。

  • 自分の親（基本ケース）、または
  • 自分の親の先祖（再帰的ステップ）。

フィボナッチ数列は再帰のもう一つの典型的な例です。

基本ケース1としてFib(0) = 0 、
基本ケース2としてFib(1) = 1 、
すべての整数n > 1に対して、Fib( n ) = Fib( n −1) + Fib( n −2)です。

多くの数学公理は再帰的な規則に基づいています。例えば、ペアノ公理による自然数の正式な定義は、「0は自然数であり、それぞれの自然数には、やはり自然数である次の数が存在する」と記述できます。[ 2 ]この基本ケースと再帰的な規則によって、すべての自然数の集合を生成することができます。

再帰的に定義されたその他の数学オブジェクトには、階乗、関数(例:再帰関係)、集合(例:カントール三元集合)、フラクタルなどがあります。

再帰には、もっと冗談めいた定義もいろいろあります。「再帰的なユーモア」を参照してください。

非公式の定義

サワードウ スターターを小麦粉に混ぜてサワードウを作る工程。レシピでは、前回同じレシピを作ったときに残ったサワードウを使用します。

再帰とは、ある手続きのステップの一つが、その手続き自身を呼び出すことを含む場合に、その手続きが行う処理のことである。再帰を経る手続きは「再帰的」であると言われる。[ 3 ]

再帰を理解するには、手続きと手続きの実行の違いを認識する必要があります。手続きとは、一連の規則に基づく一連のステップであり、手続きの実行とは、実際に規則に従ってステップを実行することです。

再帰は、あるプロシージャの仕様内で他のプロシージャの実行を参照することと関連していますが、同じではありません。

手順がこのように定義されると、すぐに無限ループの可能性が生じます。再帰は、手順が完了できるように特定のケースで問題のステップがスキップされる場合にのみ、定義で適切に使用できます。

再帰的な手続きは、たとえ適切に定義されたとしても、人間にとって容易ではありません。なぜなら、手続きの新たな呼び出しと、既に実行中の手続きの呼び出しを区別する必要があるからです。そのためには、複数の同時インスタンスがどの程度まで進行しているかを管理する作業が必要になります。そのため、日常的な状況で再帰的な定義が行われることは稀です。

言語において

言語学者ノーム・チョムスキーは、他の多くの人々とともに、言語における文法的な文の数に上限がないこと、そして文法的な文の長さに上限がないこと（文を発話するのに利用できる時間などの実際的な制約以外）は、自然言語における再帰の結果として説明できると主張している。[ 4 ] [ 5 ]

これは、文のような統語範疇の再帰的定義という観点から理解できます。文は、動詞の後に別の文が続く構造を持つ場合があります。例えば、「ドロシーは魔女は危険だと思っている」という文では、 「魔女は危険だ」という文がより大きな文の中に出現します。つまり、文は（非常に大まかに言えば）名詞句、動詞、そして必要に応じて別の文を含む構造を持つものとして再帰的に定義できます。これは、数学的な再帰の定義の特殊なケースに過ぎません。

これは言語の創造性、つまり文法的な文の無限の数を理解する一つの方法を提供する。なぜなら、文の長さは任意になり得ると直ちに予測できるからである。ドロシーはトトがブリキの木こりが…と言ったのではないかと疑っていると思う。文以外にも再帰的に定義できる構造は多く存在し、したがって文の中で一つのカテゴリーのインスタンスを別のカテゴリーに埋め込む方法も数多く存在する。[ 6 ]長年にわたり、言語全般がこの種の分析に適していることが証明されてきた。

再帰は人間の言語の本質的な性質であるという、一般的に受け入れられている考えは、ダニエル・エヴェレットによって、ピダハン語に関する自身の主張に基づいて異議を唱えられた。アンドリュー・ネヴィンズ、デイヴィッド・ペセツキー、シレーヌ・ロドリゲスなど、これに反論する者は数多くいる。[ 7 ]文学における自己言及は、いずれにせよ、数学的あるいは論理的な再帰とは性質が異なると主張できる。[ 8 ]

再帰は統語論だけでなく自然言語の意味論でも重要な役割を果たしている。例えば、 andという単語は、文の意味に適用して新しい文を作ることができる関数として解釈することができ、同様に名詞句の意味、動詞句の意味などにも適用できる。また、自動詞、他動詞、二他動詞にも適用できる。再帰に適切な柔軟性を備えた単一の表示を与えるために、通常はこれらの異なるタイプの意味を引数として取ることができるように定義される。これは、文を組み合わせる単純なケースを定義し、次に他のケースをその単純なケースに基づいて再帰的に定義することによって行うことができる。[ 9 ]

再帰文法は再帰的な生成規則を含む形式文法である。[ 10 ]

再帰的なユーモア

再帰は、コンピュータサイエンス、プログラミング、哲学、数学の教科書などで、ユーモラスな意味合いで使われることがあります。一般的には、循環的な定義や自己参照が用いられ、想定される再帰ステップが基底ケースに近づくどころか、無限後退に陥るというものです。このような書籍の用語集に、次のようなジョーク的な項目が含まれていることは珍しくありません。

再帰については、「再帰」を参照。[ 11 ]

ブライアン・カーニハンとデニス・リッチーの共著『プログラミング言語 C』 のいくつかの版の索引269ページに、このジョークのバリエーションが見られる。索引のエントリが自分自身を再帰的に参照している（「再帰 86、139、141、182、202、269」）。このジョークの初期のバージョンは、ローラン・シクロッシーの『Let's talk Lisp』（プレンティス・ホール・プロダクション社より1975年12月1日出版、著作権取得日1976年）やカーニハンとプラウガーの共著『Software Tools』（アディソン・ウェズリー・プロフェッショナル社より1976年1月11日出版）に見られる。このジョークはカーニハンとパイクの共著『UNIXプログラミング環境』にも登場する。 『プログラミング言語 C』の初版には登場していない。このジョークは関数型プログラミングの伝承の一部であり、前述の本の出版以前から関数型プログラミングのコミュニティで既に広まっていた。[ 12 ] [ 13 ]

トロント再帰的歴史プロジェクトの記念として設置された銘板。トロント再帰的歴史プロジェクトとは、トロントの再帰的歴史を記念するものです。

もう一つのジョークは「再帰を理解するには、再帰を理解しなければならない」というものである。[ 11 ]英語版の Google ウェブ検索エンジンでは、「再帰」を検索すると、サイトが「もしかして:再帰」と提案する。[ 14 ]アンドリュー・プロトキンによる別の形式は次の通りである。 「再帰が何であるかをすでに知っている場合は、答えを覚えておいてください。そうでない場合は、ダグラス・ホフスタッターにあなたよりも近くに立っている人を見つけて、その人に再帰が何であるか聞いてください。」

再帰的な頭字語もまた、再帰的なユーモアの例です。例えば、PHPは「PHP Hypertext Preprocessor（PHPハイパーテキストプリプロセッサ）」、 WINEは「WINE Is Not an Emulator（WINEはエミュレータではない）」、GNU は「GNUはUnixではない」、SPARQL は「SPARQLプロトコルとRDFクエリ言語」を表します。

数学では

シェルピンスキー三角形—フラクタルを形成する三角形の限定された再帰

再帰的に定義された集合

例:自然数

再帰的に定義された集合の標準的な例は、自然数によって与えられます。

0は北{\displaystyle \mathbb {N} }
nが に含まれる場合、n + 1 は に含まれる北{\displaystyle \mathbb {N} }北{\displaystyle \mathbb {N} }
自然数の集合は、前の 2 つの特性を満たす最小の集合です。

数理論理学において、ペアノ公理（ペアノの公理、あるいはペアノの公理、デデキント・ペアノの公理）は、19世紀にドイツの数学者リヒャルト・デデキントとイタリアの数学者ジュゼッペ・ペアノによって提唱された自然数の公理である。ペアノの公理は、再帰的な後続関数と、再帰関数としての加算および乗算を参照することで自然数を定義する。

例: 証明手順

もう 1 つの興味深い例は、次のように帰納的に (または再帰的に) 定義される 証明手順に基づいて定義される公理システム内のすべての「証明可能な」命題の集合です。

  • 命題が公理である場合、それは証明可能な命題です。
  • 命題が推論規則によって真に到達可能な命題から導き出せる場合、その命題は証明可能な命題です。
  • 証明可能な命題の集合は、これらの条件を満たす命題の最小の集合です。

有限分割規則

有限分割規則は幾何学的な再帰の一種であり、フラクタルのような画像を作成するために使用できます。分割規則は、有限個のラベルが付けられたポリゴンの集合から始まり、各ポリゴンは元のポリゴンのラベルのみに基づいて、より小さなラベル付きポリゴンに分割されます。このプロセスは反復可能です。カントール集合を​​作成するための標準的な「ミドルサード」手法は、重心分割と同様に、分割規則です。

関数型再帰

関数は、それ自身を用いて再帰的に定義されることがあります。身近な例としては、フィボナッチ数列があります：F ( n ) = F ( n − 1) + F ( n − 2)。このような定義が有用であるためには、再帰的に定義されない値に還元可能でなければなりません。この場合、F (0) = 0 およびF (1) = 1 となります。

再帰定義を含む証明

前のセクションのように、再帰的に定義された集合または関数に標準的な事例による証明手法を適用すると、構造的帰納法が得られます。これは、数理論理学やコンピュータ サイエンスで証明を導くために広く使用されている数学的帰納法の強力な一般化です。

再帰最適化

動的計画法は、多期間または多段階の最適化問題を再帰的に表現する最適化手法です。動的計画法における重要な結果はベルマン方程式であり、これは最適化問題の以前の時点（または以前のステップ）における値を、後の時点（または後のステップ）における値で表すものです。

再帰定理

集合論において、これは再帰的に定義された関数が存在することを保証する定理である。集合X 、 Xの元a、関数f : X → Xが与えられたとき、 （0を含む自然数の集合を表す） 関数が唯一存在し、F:北→X{\displaystyle F:\mathbb {N} \to X}北{\displaystyle \mathbb {N} }

F（0）＝1つの{\displaystyle F(0)=a}
F（n+1）＝f（F（n））{\displaystyle F(n+1)=f(F(n))}

任意の自然数nに対して。

デデキントは、集合論的関数の再帰による一意定義の問題を初めて提起し、1888年のエッセイ「Was sind und was sollen die Zahlen?」で議論の概要を示した。[ 15 ]北{\displaystyle \mathbb {N} }

一意性の証明

次の 2 つの関数とを取ります。F:北→X{\displaystyle F:\mathbb {N} \to X}G:北→X{\displaystyle G:\mathbb {N} \to X}

F（0）＝1つの{\displaystyle F(0)=a}
G（0）＝1つの{\displaystyle G(0)=a}
F（n+1）＝f（F（n））{\displaystyle F(n+1)=f(F(n))}
G（n+1）＝f（G（n））{\displaystyle G(n+1)=f(G(n))}

ここで、aはXの要素です。

すべての自然数 nに対してF ( n )= G ( n )であることが数学的帰納法によって証明できる。

基本ケース: F (0) = a = G (0)なので、 n = 0の場合に等式が成立します。
帰納的ステップ：ある に対してF ( k ) = G ( k )と仮定する。するとF ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1)となる。 け∈北{\displaystyle k\in \mathbb {N} }
したがって、F ( k ) = G ( k )はF ( k + 1) = G ( k + 1)を意味します。

帰納法により、すべての場合においてF ( n )= G ( n )となる。 n∈北{\displaystyle n\in \mathbb {N} }

コンピュータサイエンス

問題を単純化するための一般的な方法は、問題を同じ種類のサブ問題に分割することです。コンピュータプログラミング技術として、これは分割統治法と呼ばれ、多くの重要なアルゴリズムの設計において鍵となります。分割統治法は、問題解決におけるトップダウンアプローチとして機能し、より小さなインスタンスを解くことで問題を解決します。これとは対照的なアプローチが動的計画法です。このアプローチはボトムアップアプローチとして機能し、望ましいサイズに達するまで、より大きなインスタンスを解くことで問題を解決します。

再帰の典型的な例は、次のPythonコード で示される階乗関数の定義です。

def factorial ( n ): n > 0 の場合: n * factorial ( n - 1 )を返す、そうでない場合: 1を返す

この関数は、入力の小さいバージョンに対して自分自身を再帰的に呼び出し、階乗の数学的定義と同様に、 基本ケースに達するまで(n - 1)再帰呼び出しの結果を で乗算します。n

コンピュータプログラミングにおける再帰の好例の一つは、関数がより単純化された、多くの場合より小さなバージョンを用いて定義される場合です。問題の解は、これらのより単純なバージョンから得られた解を組み合わせることで考案されます。再帰の応用例の一つとして、プログラミング言語のパーサーが挙げられます。再帰の大きな利点は、有限のコンピュータプログラムによって、無限の文、設計、その他のデータを定義、解析、または生成できることです。

再帰関係とは、1つ以上の列を再帰的に定義する方程式です。特定の種類の再帰関係は、「解く」ことで非再帰的な定義（例えば、閉形式式）を得ることができます。

アルゴリズムにおける再帰の使用には、メリットとデメリットの両方があります。主なメリットは通常、命令の簡潔さです。主なデメリットは、再帰アルゴリズムのメモリ使用量が急速に増加する可能性があるため、大規模なインスタンスでは実用的ではないことです。

生物学では

植物や動物には、再帰的なプロセスによって形成されたように見える形状が時折見られます。例えば、1つの大きな部分が2つ以上の類似した小さな部分に枝分かれする分岐構造などが挙げられます。ロマネスコブロッコリーがその一例です。[ 16 ]

ビジネスでは

経営学では、再帰とは、大規模企業における抽象化レベルを反復するプロセスを指すことがあります。 [ 17 ]一般的な例としては、ライン管理職から上級管理職、そして中間管理職へと 至る経営階層の再帰的な性質が挙げられます。また、コーポレートガバナンスにおける資本構成というより広範な問題も包含しています。[ 18 ]

芸術においては

再帰人形：ズヴィョズドチキンとマリューチンによるマトリョーシカ人形のオリジナルセット、1892年
ジョットの「ステファネスキ三連祭壇画」 （1320 年）の前面には、中央のパネルでひざまずいている人物によって支えられている自身の像が繰り返し描かれています。

マトリョーシカ人形は再帰的な概念を物理的に表現した芸術的な例である。[ 19 ]

再帰は、1320年に制作されたジョットのステファネスキ三連祭壇画以来、絵画で使用されている。中央のパネルには、ステファネスキ枢機卿がひざまずいて三連祭壇画自体を捧げ物として掲げている姿が描かれている。[ 20 ] [ 21 ]この手法は、より一般的にはドロステ効果として知られており、ミゼ・アン・アビム技法の一例である。

MCエッシャーの版画ギャラリー（1956年）は、歪んだ都市を描いた版画で、その中にギャラリーがあり、そのギャラリーも絵を再帰的に含み、無限に続いていく。[ 22 ]

文化の中で

映画「インセプション」では、名詞に接尾辞-ceptionをつけて、何かの再帰を冗談めかして示す口語表現が使われた。 [ 23 ]

参照

参考文献

  1. ^コージー、ロバート・L. (2006). 『論理、集合、そして再帰』（第2版）. サドベリー、マサチューセッツ州: ジョーンズ・アンド・バートレット出版社. ISBN 0-7637-3784-4. OCLC  62093042 .
  2. ^ 「ペアノの公理 | 数学」ブリタニカ百科事典。2019年10月24日閲覧。
  3. ^ 「RECURSIVEの定義」 www.merriam-webster.com . 2019年10月24日閲覧。
  4. ^ピンカー、スティーブン（1994）『言語本能』ウィリアム・モロー著。
  5. ^ピンカー、スティーブン；ジャッケンドフ、レイ (2005). 「言語能力：何がそんなに特別なのか？」認知95 ( 2): 201– 236. CiteSeerX 10.1.1.116.7784 . doi : 10.1016/j.cognition.2004.08.004 . PMID 15694646 . S2CID 1599505 .   
  6. ^ Nordquist, Richard. 「英語文法における再帰とは何か？」 ThoughtCo . 2019年10月24日閲覧。
  7. ^ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). 「証拠と議論：Everett (2009)への返答」（PDF） . Language . 85 (3): 671– 681. doi : 10.1353/lan.0.0140 . S2CID 16915455. 2012年1月6日時点のオリジナル（PDF）からアーカイブ。 
  8. ^ドラッカー、トーマス（2008年1月4日）『数理論理学の歴史の展望』シュプリンガー・サイエンス＆ビジネス・メディア、110頁。ISBN 978-0-8176-4768-1。
  9. ^ Barbara ParteeとMats Rooth。1983年。Rainer Bäuerle他著『言語の意味、使用、解釈』。Paul PortnerとBarbara Partee編著『形式意味論：必須読本』に再録。Blackwell。
  10. ^ Nederhof, Mark-Jan; Satta, Giorgio (2002)、「非再帰文脈自由文法の解析」、第40回計算言語学協会年次会議論文集 (ACL '02)、ペンシルベニア州ストウズバーグ、米国：計算言語学協会、pp.  112– 119、doi : 10.3115/1073083.1073104。
  11. ^ a bハンター、デイビッド (2011). 『離散数学の基礎』ジョーンズ＆バートレット. p. 494. ISBN 9781449604424。
  12. ^ Shaffer, Eric. 「CS 173:離散構造」(PDF) . イリノイ大学アーバナ・シャンペーン校. 2023年7月7日閲覧。
  13. ^ 「C言語によるコンピュータサイエンスとプログラミング入門；セッション8：2008年9月25日」（PDF）コロンビア大学。 2023年7月7日閲覧。
  14. ^ 「再帰 - Google 検索」 . www.google.com . 2019年10月24日閲覧。
  15. ^ A. Kanamori, " In Praise of Replacement ", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). 2023年8月21日にアクセス。
  16. ^ 「本日の写真：フラクタルカリフラワー」 2012年12月28日. 2020年4月19日閲覧。
  17. ^ライディング、アラン；ヘインズ、ジョージ・H；トーマス、ローランド（1994）「カナダの中小企業と銀行のインターフェース：再帰モデル」『起業家精神の理論と実践』18（4）SAGEジャーナル：5 ～ 24。doi ：10.1177/104225879401800401。
  18. ^ビア、スタッフォード（1972年）『ブレイン・オブ・ザ・ファーム』ジョン・ワイリー・アンド・サンズ、ISBN 978-0471948391。
  19. ^ Tang, Daisy (2013年3月). 「CS240 -- 講義ノート: 再帰」 . カリフォルニア州立工科大学ポモナ校. 2018年3月17日時点のオリジナルよりアーカイブ. 2015年9月24日閲覧.再帰のその他の例：ロシアのマトリョーシカ人形。人形はそれぞれ無垢材で作られているか、中が空洞で中に別のマトリョーシカ人形が入っています。
  20. ^ 「ジョット・ディ・ボンドーネと助手たち：ステファネスキ三連祭壇画」バチカン2015年9月16日閲覧。
  21. ^スヴォジル、カール (2018). 『物理的(A)因果性：決定論、ランダム性、そして原因のない出来事』 シュプリンガー. p. 12. ISBN 9783319708157。
  22. ^ Cooper, Jonathan (2007年9月5日). 「芸術と数学」 . 2020年7月5日閲覧。
  23. ^ 「-ception – ライス大学新語データベース」ライス大学。2017年7月5日時点のオリジナルよりアーカイブ。2016年12月23日閲覧。

参考文献

ウィキメディア コモンズには、再帰に関連するメディアがあります。
無料辞書の Wiktionary で「recursion」 または「recursivity」を調べてください。
「 https://en.wikipedia.org/w/index.php?title=再帰&oldid =1331298925」より取得