再帰

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

ドロステ効果として知られる視覚的な再帰形式この画像の女性は、同じオブジェクトを持っている自分の小さな画像を含むオブジェクトを持っています。次に、同じオブジェクトを持っている自分の小さな画像などが含まれています。1904年JanMissetによって設計されたドロステココアスズ

再帰(形容詞:再帰)は、モノがそれ自体またはそのタイプの観点から定義されている場合に発生します。再帰は、言語学から論理学に至るまで、さまざまな分野で使用されています。再帰の最も一般的なアプリケーションは、数学コンピューターサイエンスであり、定義されている関数はそれ自体の定義内で適用されます。これは明らかに無限の数のインスタンス(関数値)を定義しますが、多くの場合、無限ループや参照の無限チェーンが発生しないように行われます。

正式な定義

ウロボロス、自分の尻尾を食べる蛇やドラゴンを描いた古代のシンボル。

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

  • 単純な基本ケース(または複数のケース)—再帰を使用して回答を生成しない終了シナリオ
  • 再帰的ステップ連続するすべてのケースを基本ケースに向けて減らす一連のルール。

たとえば、以下は人の祖先の再帰的定義です。祖先は次のいずれかです。

  • 親(基本ケース)、または
  • 親の祖先(再帰的ステップ)。

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

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

多くの数学的公理は再帰的な規則に基づいています。たとえば、ペアノの公理による自然数の正式な定義は、 「ゼロは自然数であり、各自然数には後継者があり、これも自然数です」と説明できます。[1]この基本ケースと再帰規則により、すべての自然数のセットを生成できます。

他の再帰的に定義された数学的対象には、階乗関数(たとえば、漸化式)、集合(たとえば、Cantor ternary set)、およびフラクタルが含まれます。

再帰には、さらにさまざまな定義があります。再帰的なユーモアを参照してください

非公式の定義

最近リフレッシュされたサワードウ、発酵によって泡立つ:レシピは、同じレシピが最後に作られたときから残っているサワードウを必要とします。

再帰とは、手順のステップの1つに手順自体の呼び出しが含まれる場合に、手順が通過するプロセスです。再帰を経る手順は「再帰的」と呼ばれます。[2]

再帰を理解するには、プロシージャとプロシージャの実行の違いを認識する必要があります。プロシージャは、一連のルールに基づく一連のステップですが、プロシージャの実行には、実際にルールに従い、ステップを実行することが含まれます。

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

プロシージャがそのように定義されている場合、これはすぐに無限ループの可能性を生み出します。再帰は、手順を完了できるように特定の場合に問題のステップがスキップされた場合にのみ、定義で適切に使用できます。

しかし、それが適切に定義されていても、再帰的プロシージャは、新しいものと古い部分的に実行されたプロシージャの呼び出しを区別する必要があるため、人間が実行するのは簡単ではありません。これには、手順のさまざまな同時インスタンスがどこまで進行したかについて、ある程度の管理が必要です。このため、再帰的な定義は日常の状況では非常にまれです。

言語で

言語学者のノーム・チョムスキーは、とりわけ、言語の文法文の数に上限がないこと、および文法文の長さに上限がないこと(1つを発するのに利用できる時間などの実際的な制約を超えている)を主張しています)、自然言語での再帰の結果として説明することができます。[3] [4]

これは、文などの構文カテゴリの再帰的定義の観点から理解できます。文は、動詞に続くものが別の文であるという構造を持つことができます。ドロシーは魔女は危険であると考えています。魔女が危険あるという文は、大きい方の文で発生します。したがって、文は、名詞句、動詞、およびオプションで別の文を含む構造を持つものとして再帰的に(非常に大まかに)定義できます。これは実際には、再帰の数学的定義の特殊なケースにすぎません。

これは、言語の創造性、つまり無制限の数の文法文を理解する方法を提供します。これは、文が任意の長さになる可能性があることを即座に予測するためです。ドロシーは、トトがティンマンが言ったことを疑っていると考えています再帰的に定義できる文以外にも多くの構造があり、したがって、文が1つのカテゴリのインスタンスを別のカテゴリの中に埋め込むことができる多くの方法があります。[5]何年にもわたって、言語は一般的にこの種の分析に適していることが証明されてきました。

しかし、最近、再帰は人間の言語の本質的な特性であるという一般的に受け入れられている考えは、ピダハン語に関する彼の主張に基づいてダニエル・エベレットによって異議を唱えられました。Andrew Nevins、David Pesetsky、Cilene Rodriguesは、これに反対している多くの人の中にいます。[6]文学的な自己参照は、いかなる場合でも、数学的または論理的な再帰とは種類が異なると主張することができます。[7]

再帰は、構文だけでなく、自然言語のセマンティクスでも重要な役割を果たします。たとえば、単語は、文の意味に適用して新しい文を作成できる関数として解釈できます。同様に、名詞句の意味、動詞句の意味などにも適用できます。自動詞、他動詞、または二重他動詞にも適用できます。適切に柔軟であり、通常、これらのさまざまなタイプの意味のいずれかを引数として取ることができるように定義されている単一の表示を提供するため。これは、文を組み合わせる単純なケースに対して定義し、次に他のケースを単純なケースに関して再帰的に定義することによって行うことができます。[8]

再帰的文法は、再帰的生成規則を含む正式な文法です[9]

再帰的なユーモア

再帰的なウィキペディアのページ

再帰は、コンピュータサイエンス、プログラミング、哲学、または数学の教科書で、一般に循環定義または自己参照を与えることによってユーモラスに使用されることがあります。この場合、推定される再帰ステップは基本ケースに近づきませんが、代わりに無限後退につながります。 。そのような本が次の行に沿って用語集にジョークエントリを含めることは珍しいことではありません。

再帰。再帰を参照してください。[10]

ブライアン・カーニハンデニス・リッチーの著書「Cプログラミング言語」の 一部の版の索引の269ページにバリエーションがあります。インデックスエントリはそれ自体を再帰的に参照します(「再帰86、139、141、182、202、269」)。このジョークの初期のバージョンは、 Lat 's talkLispのLaurentSiklóssy(1975年12月1日にPrentice Hall PTRが発行、著作権は1976年)およびKernighanとPlaugerのSoftware Tools(Addison-WesleyProfessionalが発行)にあります。 1976年1月11日)。このジョークは、KernighanとPikeによるUNIXプログラミング環境にも登場します。Cプログラミング言語の初版には表示されませんでしたこのジョークは関数型プログラミングの民間伝承の一部であり、前述の本が出版される前から関数型プログラミングコミュニティですでに広まっています。

もう1つの冗談は、「再帰を理解するには、再帰を理解する必要がある」というものです。[10]英語版のGoogleWeb検索エンジンでは、「再帰」を検索すると、サイトは「つまり、再帰」と表示します[11]別の形式は、Andrew Plotkinによるものです。「再帰とは何かをすでに知っている場合は、答えを覚えておいてください。そうでない場合は、自分よりもダグラス・ホフスタッターの近くに立っている人を見つけて、その再帰を尋ねてください。は。"

再帰的頭字語は、再帰的ユーモアの他の例です。たとえば、PHPは「PHPHypertext Preprocessor」を表し、WINE「WINEIs Not a Emulator」を表し、 GNUは「GNU'snot Unix」を表し、 SPARQLは「SPARQLプロトコルとRDFクエリ言語」を表します。

数学では

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

再帰的に定義されたセット

例:自然数

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

0は
nが入っている場合、次にn +1が
自然数のセットは、前の2つのプロパティを満たす最小のセットです。

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

例:証明手順

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

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

有限細分化ルール

有限細分割ルールは、フラクタルのような画像を作成するために使用できる再帰の幾何学的形式です。サブディビジョンルールは、有限数のラベルでラベル付けされたポリゴンのコレクションから始まり、各ポリゴンは、元のポリゴンのラベルのみに依存する方法で、より小さなラベル付きポリゴンにサブディバイドされます。このプロセスは繰り返すことができます。カントール集合を​​作成するための標準的な「ミドルサード」手法は、重心細分と同様に、細分規則です。

機能的再帰

関数は、それ自体に関して再帰的に定義できます。おなじみの例は、フィボナッチ数列です:Fn)= Fn − 1)+ Fn − 2)。このような定義が役立つためには、再帰的に定義されていない値に還元できる必要があります。この場合、F(0)= 0およびF(1)= 1です。

有名な再帰関数はアッカーマン関数です。これは、フィボナッチ数列とは異なり、再帰なしでは表現できません。[要出典]

再帰的定義を含む証明

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

再帰的最適化

動的計画法は、多期間または多段階の最適化問題を再帰的な形で言い換える最適化へのアプローチです。動的計画法の重要な結果はベルマン方程式です。これは、後の時間(または後のステップ)の値に関して、前の時間(または前のステップ)の最適化問題の値を書き込みます。

再帰定理

集合論では、これは再帰的に定義された関数が存在することを保証する定理です。集合X 、 Xの要素aおよび関数fXXが与えられると、定理は一意の関数があることを示します。(どこゼロを含む自然数のセットを示します)

任意の自然数nに対して

独自性の証明

2つの機能を取るそのような:

ここで、aXの要素です。

数学的帰納法により、すべての自然数 nに対してF n = Gnであることが証明できます

基本ケースF(0)= a = G(0)なので、 n = 0に対して等式が成り立ちます
帰納的ステップ:いくつかのFk)= Gkと仮定します次に、Fk + 1)= fFk))= fGk))= Gk + 1)
したがって、 Fk)= Gk)はFk + 1)= Gk + 1 )を意味します。

誘導により、すべてのFn)= Gn

コンピュータサイエンス

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

再帰の典型的な例は、階乗関数の定義です。これは、Cコード で示されています。

unsigned int階乗unsigned int n {     
    if n == 0 {    
        1を返します; 
    } else {  
        n *階乗n --1 );を返します。     
    }
}

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

コンピュータープログラミングの再帰は、関数がそれ自体のより単純な、多くの場合はより小さなバージョンの観点から定義されている場合に例示されます。次に、問題のより単純なバージョンから得られた解決策を組み合わせることによって、問題の解決策が考案されます。再帰のアプリケーションの例の1つは、プログラミング言語のパーサーです。再帰の大きな利点は、可能な文、デザイン、またはその他のデータの無限のセットを、有限のコンピュータープログラムによって定義、解析、または生成できることです。

漸化式は、1つ以上のシーケンスを再帰的に定義する方程式です。いくつかの特定の種類の漸化式を「解決」して、非再帰的な定義を取得できます(たとえば、閉じた形式の式)。

アルゴリズムで再帰を使用することには、長所と短所の両方があります。主な利点は、通常、指示が簡単なことです。主な欠点は、再帰的アルゴリズムのメモリ使用量が非常に急速に増加し、より大きなインスタンスでは実用的でない可能性があることです。

生物学では

再帰的なプロセスによって作成されたように見える形状は、1つの大きな部分が2つ以上の同様の小さな部分に分岐する分岐構造など、植物や動物に現れることがあります。一例はロマネスコブロッコリーです。[12]

アートで

Recursive dolls:ZvyozdochkinMalyutinによるMatryoshka人形のオリジナルセット、1892年
ジョットステファネスキ三連祭壇画、1320年の正面には、再帰的に自分自身のイメージが含まれています(中央のパネルのひざまずく人物によって支えられています)。

ロシアの人形またはマトリョーシカ人形は、再帰的な概念の物理的な芸術的な例です。[13]

再帰は、1320年に作られたジョットステファネスキ三連祭壇画以来、絵画で使用されています。その中央のパネルには、三連祭壇画自体を供物として掲げているステファネスキ枢機卿のひざまずく姿が含まれています。[14] [検証に失敗しました]

MC Escherプリントギャラリー(1956)は、画像を再帰的に含むギャラリーを含む歪んだ都市を描いたプリントであり、無限に続きます。[15]

も参照してください

参考文献

  1. ^ 「ペアノの公理|数学」ブリタニカ百科事典2019年10月24日取得
  2. ^ 「再帰の定義」www.merriam-webster.com 2019年10月24日取得
  3. ^ ピンカー、スティーブン(1994)。言語本能ウィリアムモロー。
  4. ^ ピンカー、スティーブン; レイ・ジャッケンドフ(2005)「語学部:何がそんなに特別なの?」認知95(2):201–236。CiteSeerX10.1.1.116.7784_ 土井10.1016 /j.cognition.2004.08.004PMID15694646_ S2CID1599505_   
  5. ^ ノードクイスト、リチャード。「英文法の再帰とは?」ThoughtCo 2019年10月24日取得
  6. ^ ネビンス、アンドリュー; ペセツキー、デビッド; Rodrigues、Cilene(2009)。「証拠と議論:エベレットへの回答(2009)」(PDF)言語85(3):671–681。土井10.1353 /lan.0.0140S2CID16915455_ 2012年1月6日にオリジナル(PDF)からアーカイブされました  
  7. ^ Drucker、Thomas(2008年1月4日)。数理論理学の歴史に関する展望シュプリンガーサイエンス&ビジネスメディア。p。110. ISBN 978-0-8176-4768-1
  8. ^ バーバラ・パーティーとマット・ルース。1983.RainerBäuerleetal。、 Meaning、Use、and Interpretation ofLanguageポール・ポートナーとバーバラ・パーティー編に転載。2002.正式なセマンティクス:エッセンシャルリーディングブラックウェル。
  9. ^ Nederhof、Mark-Jan; Satta、Giorgio(2002)、 "Parsing Non-recursive Context-free Grammars"、Proceedings of the 40th Annual Meeting on Association for Computational Linguistics(ACL '02)、Stroudsburg、PA、USA:Association for Computational Linguistics、pp。112– 119、doi10.3115 / 1073083.1073104
  10. ^ a b ハンター、デビッド(2011)。ディスクリート数学の要点ジョーンズとバートレット。p。494. ISBN 9781449604424
  11. ^ 「再帰-Google検索」www.google.com 2019年10月24日取得
  12. ^ 「今日の写真:フラクタルカリフラワー」2012年12月28日2020年4月19日取得
  13. ^ 唐、デイジー。「再帰」2015年9月24日取得再帰のその他の例:ロシアのマトリョーシカ人形。各人形は無垢材または中空で、その中に別のマトリョーシカ人形が含まれています。
  14. ^ 「ジョットディボンドーネとアシスタント:ステファネスキ三連祭壇画」バチカン2015年9月16日取得
  15. ^ クーパー、ジョナサン(2007年9月5日)。「芸術と数学」2020年7月5日取得

参考文献

外部リンク