再帰再帰の概要

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

定義

平行な合わせ鏡の間に物体を置くと、その像が鏡の中に無限に映し出される。このように、あるものが部分的にそれ自身で構成されていたり、それ自身によって定義されている時に、それを「再帰的(Recursive)」だという^[1]^[2]。論理的思考の重要な特質のひとつであり、数学では漸化式や数学的帰納法が再帰的構造を持っている^[1]。計算機科学だと、オブジェクトやメソッドのクラスが、以下2つの項目で定義できる場合に再帰的構造だと言える。

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

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

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

フィボナッチ数列は、再帰を用いた古典的な数式例である。

基底1として
$Fib(0)=0$
再帰的なウィキペディアのページ。

たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義や自己参照が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。
- 再帰については「再帰」を参照のこと^[10]。
これは想定した再帰段階が基底段階へと帰着することなく、無限後退を引き起こすという（プログラミング失敗例の）洒落である。この手の最初のジョークは1975-76年に出版されたプログラム言語の教本『Let's talk Lisp 』と『in Software Tools』に見られる。これは関数型プログラミングを伝授する一環としての洒落で、上の書籍が出版される前に（米国の）プログラミング関連コミュニティで既に広まっていた。
もう一つの冗談が「再帰を理解するには、再帰を理解する必要がある」^[10]というものである。英語版Googleウェブ検索エンジンで"recursion"を検索すると、同サイトでは一番上に"Did you mean: recursion（再帰って意味だったかな）"と赤く表示される^[11]^{[注釈 2]}。
再帰的頭字語は、再帰を含んだ洒落の例である。例えば、PHP (プログラミング言語)は"PHP Hypertext Preprocessor"の略で、WINEは"WINE Is Not an Emulator"、GNUは"GNU's not Unix"を表す。

脚注
注釈
1. ^ 記述している対象と同義な性質・情報を有する（幾何学でいう相似関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう合同図形）は参照に含めない。
2. ^ 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。
3. ^ なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば数論や解析学では一般に0を含めない）。詳細は自然数を参照。
4. ^ フィボナッチ数列の非再帰的な一般項は、次の通り^[12]: $F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}$ 　
出典
1. ^ ^a ^b 林創「再帰呼び出しを含む手続き処理の難しさ」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁
2. ^ Wirth,N.(1986)Algorithms & Data Structures（浦昭二・国府方久史　訳『アルゴリズムとデータ構造』東京近代科学社、1990年）
3. ^ “Peano axioms | mathematics” (英語). Encyclopedia Britannica. 2019年10月24日閲覧。
4. ^ Pinker, Steven (1994). The Language Instinct. William Morrow
5. ^ Pinker, Steven; Jackendoff, Ray (2005). “The faculty of language: What's so special about it?”. Cognition 95 (2): 201?236. doi:10.1016/j.cognition.2004.08.004. PMID 15694646.
6. ^ Nordquist, Richard. “What Is Recursion in English Grammar?” (英語). ThoughtCo. 2019年10月24日閲覧。
7. ^ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). “Evidence and argumentation: A reply to Everett (2009)”. Language 85 (3): 671?681. doi:10.1353/lan.0.0140. オリジナルの2012-01-06時点におけるアーカイブ。.
8. ^ Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1
9. ^ 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.
10. ^ ^a ^b Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. pp. 494. ISBN 9781449604424
11. ^ “recursion - Google Search”. www.google.com. 2019年10月24日閲覧。
12. ^ 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1。
13. ^ 百物語改め「九一三・六物語」「アッカーマン関数の漸化式による説明、数列・カリー化」2015年1月27日
14. ^ “Picture of the Day: Fractal Cauliflower” (2012年12月28日). 2020年4月19日閲覧。
15. ^ “Recursion”. 2015年9月24日閲覧。 “More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.”
16. ^ “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 2015年9月16日閲覧。
17. ^ Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events. Springer. pp. 12
18. ^ “Art and Mathematics” (2007年9月5日). 2020年7月5日閲覧。
19. ^ ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】」2022年3月24日
20. ^ 数学における落語『頭山』の世界自分自身を使って自分を定義する2023年9月8日閲覧。
21. ^ 地球にやさしいアルゴリズム第6回上手なアルゴリズムの見つけ方2023年9月8日閲覧。
22. ^ タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】」2020年5月21日
[前の解説]
[続きの解説]
「再帰」の続きの解説一覧
- 1 再帰とは
- 2 再帰の概要
- 3 数学
- 4 計算機科学
- 5 生物学
- 6 関連項目

[1] 記述している対象と同義な性質・情報を有する（幾何学でいう相似関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう合同図形）は参照に含めない。

[13] 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。

[14] なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば数論や解析学では一般に0を含めない）。詳細は自然数を参照。

[16] フィボナッチ数列の非再帰的な一般項は、次の通り^[12]: $F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}$ 　

[HH-2] 林創「再帰呼び出しを含む手続き処理の難しさ」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁

[3] Wirth,N.(1986)Algorithms & Data Structures（浦昭二・国府方久史　訳『アルゴリズムとデータ構造』東京近代科学社、1990年）

[4] “Peano axioms | mathematics” (英語). Encyclopedia Britannica. 2019年10月24日閲覧。

[5] Pinker, Steven (1994). The Language Instinct. William Morrow

[6] Pinker, Steven; Jackendoff, Ray (2005). “The faculty of language: What's so special about it?”. Cognition 95 (2): 201?236. doi:10.1016/j.cognition.2004.08.004. PMID 15694646.

[7] Nordquist, Richard. “What Is Recursion in English Grammar?” (英語). ThoughtCo. 2019年10月24日閲覧。

[8] Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). “Evidence and argumentation: A reply to Everett (2009)”. Language 85 (3): 671?681. doi:10.1353/lan.0.0140. オリジナルの2012-01-06時点におけるアーカイブ。.

[Drucker2008-9] Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1

[10] 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.

[Hunter-11] Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. pp. 494. ISBN 9781449604424

[12] “recursion - Google Search”. www.google.com. 2019年10月24日閲覧。

[algo-15] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1。

[17] 百物語改め「九一三・六物語」「アッカーマン関数の漸化式による説明、数列・カリー化」2015年1月27日

[18] “Picture of the Day: Fractal Cauliflower” (2012年12月28日). 2020年4月19日閲覧。

[19] “Recursion”. 2015年9月24日閲覧。 “More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.”

[20] “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 2015年9月16日閲覧。

[21] Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events. Springer. pp. 12

[22] “Art and Mathematics” (2007年9月5日). 2020年7月5日閲覧。

[23] ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】」2022年3月24日

[24] 数学における落語『頭山』の世界自分自身を使って自分を定義する2023年9月8日閲覧。

[25] 地球にやさしいアルゴリズム第6回上手なアルゴリズムの見つけ方2023年9月8日閲覧。

[26] タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】」2020年5月21日

[1]

[2]

[10]

[11]

[注釈 2]

[12]

再帰 再帰の概要

再帰

定義

注釈

出典

「再帰」の関連用語

再帰再帰の概要