再帰のソースを表示

{{Redirect5|米澤穂信の小説|リカーシブル (小説)|リカーシブ|リカーシブル}}
'''再帰'''（さいき、{{lang-en-short|Recursion, Recursive}}）とは、ある物事について記述する際に、記述しているもの自体への[[参照 (計算機科学)|参照]]が{{Refnest|group="注釈"|記述している対象と同義な性質・情報を有する（幾何学でいう[[相似]]関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう[[合同]]図形）は参照に含めない。}}、その記述中にあらわれることをいう。

再帰は[[言語学]]から[[論理学]]に至る様々な分野で使用されている。最も一般的な適用は[[数学]]と[[計算機科学]]で、定義されている[[関数]]がそれ自身の定義の中で参照利用されている場合を言う。

==定義==
[[File:Man photographing himself in hotel bathroom with mirrors all around to generate illusion.jpg|thumb|[[合わせ鏡]]の間で撮影すると鏡像が無限に映る。]]

平行な[[合わせ鏡]]の間に物体を置くと、その像が鏡の中に無限に映し出される。このように、あるものが部分的にそれ自身で構成されていたり、それ自身によって定義されている時に、それを「再帰的(Recursive)」だと<!--[[ニクラウス・ヴィルト]]が呼ぶようになった-->いう<ref name=HH>林 創「[https://www.jstage.jst.go.jp/article/jcss/6/4/6_4_389/_pdf 再帰呼び出しを含む手続き処理の難しさ]」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁</ref><ref>Wirth,N.(1986)''Algorithms & Data Structures''（[[浦昭二]]・国府方久史　訳『アルゴリズムとデータ構造』東京近代科学社、1990年）</ref>。論理的思考の重要な特質のひとつであり、数学では[[漸化式]]や[[数学的帰納法]]が再帰的構造を持っている<ref name=HH/>。計算機科学だと、[[オブジェクト (プログラミング)|オブジェクト]]や[[メソッド (計算機科学)|メソッド]]の[[クラス (コンピュータ)|クラス]]が、以下2つの項目で定義できる場合に再帰的構造<!--recursive behaviorの意訳-->だと言える。

*単純な基底段階 ({{lang|en|base case}}) - 答えを出すのに再帰を使わない、論理展開の終着点。基底は複数あっても構わない。
*再帰段階 ({{lang|en|recursive step}}) - 後続のあらゆる事例を基底段階に帰着させる一連の法則。

例えば、これは人間の祖先の再帰的定義である。ある人物の祖先は次のいずれかになる。

*その人物の親（基底段階）、または
*その人物の親の祖先（再帰段階）。

[[フィボナッチ数列]]は、再帰を用いた古典的な数式例である。
*基底1として<math>Fib(0)=0</math>,
*基底2として<math>Fib(1)=1</math>,
*<math>n>1</math>のあらゆる[[整数]]について <math>Fib(n)=Fib(n-1)+Fib(n-2)</math>.

多くの数学的[[公理]]は、再帰を用いた法則に基づいている。例えば、[[ペアノの公理]]による自然数の正式な定義は「ゼロは自然数であり、各自然数には後続数があり、これも自然数である」と記述されうる<ref>{{Cite web|url=https://www.britannica.com/science/Peano-axioms|title=Peano axioms {{!}} mathematics|website=Encyclopedia Britannica|language=en|access-date=2019-10-24}}</ref>。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。

他にも再帰を用いて定義されている数学的対象としては、関数の[[漸化式]]、集合の[[カントール集合]]、[[フラクタル]]分野、プログラミング言語における[[階乗]]、などがある。

==言語==
言語学者[[ノーム・チョムスキー]]らは、言語において[[適格文]]の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている<ref>{{cite book|last=Pinker|first=Steven|title=The Language Instinct|year=1994|publisher=William Morrow}}</ref><ref>{{cite journal | doi = 10.1016/j.cognition.2004.08.004 | title = The faculty of language: What's so special about it? | year = 2005 | last1 = Pinker | first1=Steven | last2 = Jackendoff | first2=Ray | journal = Cognition | volume = 95 | issue = 2 | pages = 201?236 | pmid=15694646| citeseerx = 10.1.1.116.7784 | s2cid = 1599505 }}</ref>。

これは、文章など[[統語範疇]]での再帰的定義という観点から理解可能である。文章では、動詞の[[補語]]など<!--（欧米ラテン諸語の構文なら動詞の後に続くもの）-->が別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に（非常に大まかだが）定義することができる。

これは、文章が任意の長さになり得ることも意味する。例えば、英語だと[[関係代名詞]]の"that"を使うことによって、
:"Dorothy thinks that Toto suspects that Tin Man said that..."

と再帰的に文を継ぎ足すことが可能である。再帰的に定義できうる文章の他にも多くの構造があり、別の品詞に文章を組み込む方法も沢山ある（例えば[[修飾語]]を文章形式にする）。長い歳月を経て、言語には一般的にこの種の分析で順応性があることが証明されている<ref>{{Cite web|url=https://www.thoughtco.com/recursion-grammar-1691901|title=What Is Recursion in English Grammar?|last=Nordquist|first=Richard|website=ThoughtCo|language=en|access-date=2019-10-24}}</ref>。

<!--エヴェレットの異論は、再帰の説明として蛇足なため割愛-->
しかし近年、再帰が人類の言語の本来的な性質であるという一般的に受け入れられている思想は、[[ダニエル・L・エヴェレット]]によって彼の[[ピダハン語]]研究に基づく反論が行われている。アンドリュー・ネヴィンズ、デイヴィッド・ペセツキー、シリーン・ロドリゲスがこれに反対する識者達である<ref>{{cite journal |doi=10.1353/lan.0.0140 |title=Evidence and argumentation: A reply to Everett (2009) |url=http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf |year=2009 |last1=Nevins |first1=Andrew |last2=Pesetsky |first2=David |last3=Rodrigues |first3=Cilene |journal=Language |volume=85 |issue=3 |pages=671?681 |s2cid=16915455 |archive-url=https://web.archive.org/web/20120106154616/http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf |archive-date=2012-01-06}}</ref>。いずれの場合でも、文学的な[[自己言及]]は数学的・論理的な再帰とは種類が異なると論じられている<ref name="Drucker2008">{{cite book |last=Drucker|first=Thomas |title=Perspectives on the History of Mathematical Logic |url=https://books.google.com/books?id=R70M4zsVgREC&pg=PA110 |date=4 January 2008 |publisher=Springer Science & Business Media |isbn=978-0-8176-4768-1 |page=110}}</ref>。

再帰は、構文だけでなく自然言語の[[意味論 (言語学)|意味論]]においても重要な役割を果たしている。例えば[[接続詞]]"and"は、文意に沿った新しい文章を付加できる機能だと解釈することが可能で、名詞句や動詞句<!--（自動詞、他動詞、二重他動詞も可）-->などに適用できる。<!--以下は、当方の言語学知識不足のため翻訳断念。In order to provide a single denotation for it that is suitably flexible, and is typically defined so that it can take any of these different types of meanings as arguments. -->これは、文を繋げる単純な場合について定義したもので、他の接続詞は同様の観点から再帰的に定義することができる<ref>Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., ''Meaning, Use, and Interpretation of Language''. Reprinted in Paul Portner and Barbara Partee, eds. 2002. ''Formal Semantics: The Essential Readings''. Blackwell.</ref>。

===再帰を使った洒落===
[[File:Web Page.png|thumb|再帰的なウィキペディアのページ。]]
たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して[[循環定義]]や[[自己参照]]が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。

*再帰については「再帰」を参照のこと<ref name=Hunter>{{cite book|last=Hunter|first=David|title=Essentials of Discrete Mathematics|year=2011|publisher=Jones and Bartlett|pages=494|url=https://books.google.com/books?id=kuwhTxCVovQC&q=recursion+joke|isbn=9781449604424}}</ref>。

これは想定した再帰段階が基底段階へと帰着することなく、[[無限後退]]を引き起こすという（プログラミング失敗例の）洒落である。<!--[[ブライアン・カーニガン]]と[[デニス・リッチー]]の著書『The C Programming Language』の索引にある変種は割愛。-->この手の最初のジョークは1975-76年に出版されたプログラム言語の教本『Let's talk Lisp 』と『in Software Tools』に見られる。これは[[関数型プログラミング]]を伝授する一環としての洒落で、上の書籍が出版される前に（米国の）プログラミング関連コミュニティで既に広まっていた。

もう一つの冗談が「再帰を理解するには、再帰を理解する必要がある」<ref name=Hunter/>というものである。英語版Googleウェブ検索エンジンで"recursion"を検索すると、同サイトでは一番上に"Did you mean: recursion（再帰って意味だったかな）"と赤く表示される<ref>{{Cite web|url=https://www.google.com/search?gl=us&hl=en&pws=0&q=recursion&spell=1&sa=X&ved=2ahUKEwic-_KYgef5AhWhUN4KHVSGBSMQBSgAegQIAhA1&cshid=1661603029892904&biw=1050&bih=717&dpr=1|title=recursion - Google Search|website=www.google.com|access-date=2019-10-24}}</ref>{{Refnest|group="注釈"|顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。}}。

[[再帰的頭字語]]は、再帰を含んだ洒落の例である。例えば、[[PHP (プログラミング言語)]]は"PHP Hypertext Preprocessor"の略で、[[Wine|WINE]]は"WINE Is Not an Emulator"、[[GNU]]は"GNU's not Unix"を表す。

==数学==
[[File:Sierpinski triangle.svg|thumb|200px|[[シェルピンスキーのギャスケット]]-[[フラクタル]]を形成する三角形の再帰]]
日本国内の数学では、"Recursion"や"Recursive"に対して再帰の代わりに「帰納」の訳語をあてた数学用語も幾つか存在する（[[帰納的可算集合]]、[[帰納言語]]、[[帰納的関数]]など）。これは下にある「自然数の再帰的定義の例」でも分かるように、数学における再帰には[[数学的帰納法]]と原理的な共通性があるためである。

===再帰的定義===
{{Main|再帰的定義}}
====例: 自然数====
{{See also|閉包}}
再帰的に定義された集合の標準例が、[[自然数]]である。
:0 は<math>\mathbb{N}</math>に含まれる。
:仮に''n''が<math>\mathbb{N}</math>に含まれるなら、''n''+1は<math>\mathbb{N}</math>に含まれる。
:自然数の集合<math>\mathbb{N}</math>とは、上記2つの性質を満たす最小の集合である{{Refnest|group="注釈"|なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば[[数論]]や[[解析学]]では一般に0を含めない）。詳細は[[自然数]]を参照。}}。

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

====例: 証明手続き ====
もう1つの例は、以下のように帰納または再帰を用いて定義される証明手続き{{enlink|Proof procedure}}の観点から定義される[https://kotobank.jp/word/%E5%85%AC%E7%90%86%E7%9A%84%E4%BD%93%E7%B3%BB-1315822　公理体系]内のあらゆる「証明可能な」命題の集合である。
*ある命題が公理であるならば、それは証明可能な命題である。
*ある命題が推論規則によって真に到達可能な命題から導出できるなら、それは証明可能な命題である。
*証明可能な命題の集合は、これらの条件を満たす命題の最小の集合である。

===有限分割規則===
{{Main|:en:Finite subdivision rule}}
有限分割規則は再帰の幾何学的形式で、これはフラクタル模様を作図するのに使用される。分割規則は、有限に多くの[[ラベル (曖昧さ回避)|ラベル]]でラベル付けされた多角形の集まりを起点として、各多角形は最初の多角形ラベルにのみ依存する方法で、より小さなラベル付き多角形に分割される。この工程は繰り返し行うことができる。[[カントール集合]]を作るための標準的な「3等分の中央部を除去する」技法が、分割規則の例である。

===関数での再帰===
{{Main|漸化式}}
関数は自身を再帰的に定義する場合がある。とりわけ漸化式が数列を再帰的に定める数式であり、その身近な例が<math>F(n)=F(n-1)+F(n-2)</math>という[[フィボナッチ数列]]である。こうした漸化式による定義が成立する場合、その数式は再帰を用いずに定義された基底値 （フィボナッチの場合<math>F(0) = 0</math> と<math>F(1) = 1</math>）に帰着できる必要がある。また、漸化式の再帰関係を解いた場合は非再帰的な定義（一般項）を得ることが可能である{{Refnest|group="注釈"|フィボナッチ数列の非再帰的な一般項は、次の通り<ref name="algo">{{Cite book|和書 |title=C言語による最新アルゴリズム事典 |publisher=[[技術評論社]] |author=奥村晴彦|authorlink=奥村晴彦|year=1991 |page=305 |isbn=4-87408-414-1}}</ref>:
<math>F_n
= \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\}</math>　}}。

有名な再帰関数に[[アッカーマン関数]]があるが、これは[[原始再帰関数]]よりも早く増大して[[巨大数]]を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない<ref>百物語改め「九一三・六物語」「[https://blog.goo.ne.jp/lx2x5350/e/3feb3938abc7f30853aed4f6591b3b5d　アッカーマン関数の漸化式による説明、数列・カリー化]」2015年1月27日</ref>点がフィボナッチ数列とは異なる。

===再帰的定義を含む証明===
前節のような、再帰的定義がされた集合や関数に対して複数場合分けによる証明の標準的な手法を適用すると、[[構造的帰納法]]が得られる。これは[[数理論理学]]とコンピュータサイエンスで証明を導出するのに広く使用されている[[数学的帰納法]]の強力な一般化である。

===再帰を使った最適化===
[[動的計画法]]は、多周期ないし多段階の[[最適化問題]]を再帰形式で再記述する[[数理最適化]]へのアプローチ手法である。動的計画法の主な成果が[[ベルマン方程式]]で、これは最適化問題の直近時（直近段階）での値を、その次回時刻（次段階）における値の観点から記述するものである。

===再帰定理===
[[集合論]]において、これは再帰的定義がなされた関数が存在することを保証する定理である。集合 {{mvar|X}}と、{{mvar|X}}の要素 {{mvar|a}}と、関数{{math|''f'': ''X'' → ''X''}}が与えられた場合に、任意の自然数{{mvar|n}}について
:<math>F(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>

となるような一意な関数 <math>F: \N \to X</math> (where <math>\N</math>が存在する、と同定理は述べている（ここでの<math>\N</math>は、ゼロを含む自然数の集合を示す）。

===一意性の証明===
2つの関数<math>F: \N \to X</math>と<math>G: \N \to X</math> を採ると:
:<math>F(0) = a</math>
:<math>G(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
:<math>G(n + 1) = f(G(n))</math>
ここで{{mvar|a}}は{{mvar|X}}の要素である。

すべての自然数{{mvar|n}}について{{math|1=''F''(''n'') = ''G''(''n'')}} であることは数学的帰納法によって証明できる。
:'''基底段階''': {{math|1=''F''(0) = ''a'' = ''G''(0)}} だから{{math|1=''n'' = 0}}に対して等式が成り立つ。
:'''帰納段階''': ある{{nowrap|<math>k \in \N</math>.}}について{{math|1=''F''(''k'') = ''G''(''k'')}}と仮定すると、{{math|1=''F''(''k'' + 1) = ''f''(''F''(''k'')) = ''f''(''G''(''k'')) = ''G''(''k'' + 1)}}である。 
::したがって{{math|1=''F''(''k'') = ''G''(''k'')}} は {{math|1=''F''(''k'' + 1) = ''G''(''k'' + 1)}}を含んでいる。

帰納法により、全ての<math>n \in \N</math>について{{math|1=''F''(''n'') = ''G''(''n'')}}である。 

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

プログラミングの観点では、nを表現するのにn-1という参照を持ち出してくるものを「再帰」という。再帰の古典的な例としては、[[C言語]]で与えられた[[階乗]]関数の定義がある。
<syntaxhighlight lang="c">
/* 階乗 n! の計算 */
int fact(int n) {
  if (n == 0) return 1; /* 基底段階。(n = 0) の場合: 1*/
  else return fact(n - 1) * n; /* 再帰的な構造。(n > 0) の場合: n * (n - 1)!。再帰呼出し */
}
</syntaxhighlight>
この関数では、掛け算のため入力自身より小さな(n-1)という参照を再帰的に呼び出し、再帰呼び出しの結果にnを掛ける処理を、階乗の数学的定義と同じく基底段階の値に達するまで実行する。

[[アルゴリズム]]における再帰の使用には、長所も短所もある。主な長所は、一般に命令の単純さである。主な短所は、自身を呼び出す手法なので引数が再帰終了条件を満たさない状況を避けるよう値の変化に注意する必要があること。また、再帰アルゴリズムのメモリ使用量が著しく激増して負荷がかかるため、大規模なインスタンスを扱うには非実用的な点である。

=== 再帰呼出し ===
手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム（再帰的アルゴリズム）を記述するのに適している。

複数の手続き／関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し（[[相互再帰]]）である。C言語での例：
<syntaxhighlight lang="C">
void a() {
    b();
}
void b() {
    a();
}
</syntaxhighlight>

処理を中断・終了する基底条件が必ず1つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある（[[暴走#電気・電子回路における暴走|暴走]]）。無限再帰に陥ると、[[スタックオーバーフロー]]によりプログラムが異常終了したり、システムが停止したりする原因となる。

=== 再帰的データ構造 ===
{{see also|再帰データ型}}
[[連結リスト]]や[[木構造 (データ構造)|木構造]]は、要素（ノード）の型の中にその要素型自身への参照（[[自己参照]]）が存在するようなデータ型を用いて実現される。これは再帰的データ構造（[[再帰データ型]]）である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。

下記は [[Java]] での例。Tree のクラス定義の中で Tree を使用している。
<syntaxhighlight lang="Java">
class Tree {
    Tree[] children;
}
</syntaxhighlight>

==生物学==
ある大きな部位が複数の小さな[[自己相似]]に分岐する構造（[[フラクタル]]）など、再帰的な過程によって生じたと思われる形状が、植物や動物で時々見られる。野菜の[[ロマネスコ]]がその一例である<ref>{{cite web |title=Picture of the Day: Fractal Cauliflower |date=28 December 2012 |url=https://twistedsifter.com/2012/12/fractal-cauliflower-romanesco-broccoli/ |access-date=19 April 2020}}</ref>

==芸術==
[[File:First matryoshka museum doll open.jpg|thumb|再帰的な人形の例:一組の[[マトリョーシカ人形]](1892年)]]
[[File:Droste.jpg|thumb|[[ドロステ効果]]と呼ばれる再帰の視覚形式。この[[ココア]]箱に描かれた女性の持つ盆の上にあるココア箱には、再び同じ構図の絵が描かれている。ジャン・ミュゼ画(1904)]]
{{See also|ドロステ効果}}

ロシアで生まれた[[マトリョーシカ人形]]は、再帰という概念の物理的造形例で<ref>{{cite web |last1=Tang |first1=Daisy |title=Recursion |url=http://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm |access-date=24 September 2015 |quote=More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.}}</ref>、日本ではこうした形式を「[[入れ子]]細工」とも呼んでいる。

再帰は、1320年に作られた[[ジョット・ディ・ボンドーネ|ジョット]]の三連祭壇画{{enlink|Stefaneschi Triptych}}以来、絵画で使用されている。この中央パネルにはステファネスキ枢機卿のひざまずく姿があり、三連祭壇画自体を供物として掲げている<ref>{{cite web |title=Giotto di Bondone and assistants: Stefaneschi triptych |url=http://mv.vatican.va/3_EN/pages/PIN/PIN_Sala02_03.html |publisher=The Vatican |access-date=16 September 2015}}</ref><ref>{{Cite book |title=Physical (A)Causality: Determinism, Randomness and Uncaused Events |url=https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12 |first=Karl |last=Svozil |year=2018 |publisher=Springer |pages=12}}</ref>。この手法は一般的に[[ドロステ効果]]と通称されており、[[紋中紋]]技法の一例である。

[[マウリッツ・エッシャー]]による1956年の作品{{enlink|Print Gallery (M. C. Escher)}}は、再帰的な絵を飾った画廊を含む歪んだ都市を描いた版画で、無限に堂々巡りする構図となっている<ref>{{cite web |last1=Cooper |first1=Jonathan |title=Art and Mathematics |url=https://unwrappingart.com/art/art-and-mathematics/ |access-date=5 July 2020 |date=5 September 2007}}</ref>。

日本の文芸作品では、[[夢野久作]]の『[[ドグラ・マグラ]]』が再帰的である。本作の序盤に、記憶喪失の青年は『ドグラ・マグラ』なる小説（記憶喪失の精神患者が書いたもの）を見つけることになり、この作中作に綴られている展開や結末をなぞるかのように本作も展開していき混迷の結末へ、という入れ子構造が見られる<ref>ホンシェルジュ「[https://honcierge.jp/articles/shelf_story/6278　5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】]」2022年3月24日</ref>。

落語『[[頭山]]』の、自分自身の頭に出来た池に身投げしてしまう、というサゲも、再帰的なものとして言及されることがある。<ref>[http://www.f.waseda.jp/moriya/PUBLIC_HTML/social/recursive_def.pdf 数学における 落語『頭山』の世界 自分自身を使って自分を定義する]{{Accessdate|2023-09-08}}</ref><ref>[https://xtech.nikkei.com/it/article/COLUMN/20070313/264703/ 地球にやさしいアルゴリズム 第6回 上手なアルゴリズムの見つけ方]{{Accessdate|2023-09-08}}</ref>

==類似する概念==
ここではプログラミング手続きの観点から、再帰との主な違いを述べる。
*[[回帰]] - 元々あったオブジェクト（元の位置や状態）に戻ってくる事を指す。
:対して「再帰」は元々のオブジェクトではなく、その[[参照 (計算機科学)]]にあたる小さいオブジェクトを呼び出す。

*[[帰納]] - 証明手続きの方向性として「基底段階の小さなものから段々と大きい（普遍的な）もの」へと進んでいく。特に[[数学的帰納法]]の帰納段階では、任意の自然数<math>k</math>に対して<math>P(k) \to P(k + 1)</math>が成り立つ事を示す。
:対して「再帰」のプログラムは「大きなものから、段々と小さいもの」に進んでいく<ref>タクマ「[https://suwaru.tokyo/%E3%80%90%E5%86%8D%E5%B8%B0%E7%9A%84%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%80%91%E5%86%8D%E5%B8%B0%E3%83%BB%E5%B8%B0%E7%B4%8D%E3%81%AE%E9%81%95%E3%81%84%E3%82%92%E8%A7%A3%E8%AA%AC%E3%80%90/ 【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】]」2020年5月21日</ref>。<math>P(k)</math>を計算するために<math>k-1</math>の参照オブジェクトを呼び出し、この<math>k</math>が基底段階に達するまで処理を繰り返し行う。

== 関連項目 ==
{{Div col|colwidth=20em}}
'''言語'''
* [[再帰動詞]]
* [[左再帰]]
* [[自己言及]]
* [[再帰代名詞]]
'''数学'''
* [[再帰理論]]
* [[反復関数系]]
* [[漸化式]]
* [[数学的帰納法]]
'''計算機科学'''
* [[ネスティング]]
* [[不動点コンビネータ]]
* [[無限ループ#無限再帰]]
* [[末尾再帰]]
* [[リエントラント]]
'''その他'''
* [[ドロステ効果]]/[[紋中紋]]/[[入れ子]]
* [[合わせ鏡]]/[[ビデオフィードバック]]
* [[ハノイの塔]] -解の操作手順が再帰的構造のパズル
{{Div col end}}

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈===
{{Reflist|group="注釈"}}
=== 出典 ===
{{Reflist|2}}

==外部リンク==
{{Commons category}}
{{Wiktionary}}

* [https://news.mynavi.jp/techplus/article/nadeshiko-42/　「再帰処理」を使って幾何学模様を描いてみよう] - [[マイナビ]]、関数プログラムを含めた解説
* [https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm Recursion] - tutorial by Alan Gauld
* [http://research.swtch.com/2010/03/zip-files-all-way-down.html Zip Files All The Way Down]

{{Fractals}}
{{Mathematical logic}}
{{Authority control}}

{{DEFAULTSORT:さいき}}
[[Category:再帰|*]]
[[Category:数理論理学]]
[[Category:計算理論]]
[[Category:自己言及]]
[[Category:フィードバック]]
[[Category:制御構造]]