再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/22 14:08 UTC 版)
再帰（さいき、英: Recursion, Recursive）とは、ある物事について記述する際に、記述しているもの自体への参照が[注釈 1]、その記述中にあらわれることをいう。
注釈
- ^ 記述している対象と同義な性質・情報を有する（幾何学でいう相似関係の）主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの（幾何学でいう合同図形）は参照に含めない。
- ^ 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索（自己参照）した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして：再帰」で見られる。
- ^ なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある（例えば数論や解析学では一般に0を含めない）。詳細は自然数を参照。
- ^ フィボナッチ数列の非再帰的な一般項は、次の通り[12]:
出典
- ^ a b 林 創「再帰呼び出しを含む手続き処理の難しさ」日本認知科学会『認知科学』6巻 (1999) 4号、389-405頁
- ^ Wirth,N.(1986)Algorithms & Data Structures（浦昭二・国府方久史 訳『アルゴリズムとデータ構造』東京近代科学社、1990年）
- ^ “Peano axioms | mathematics” (英語). Encyclopedia Britannica. 2019年10月24日閲覧。
- ^ Pinker, Steven (1994). The Language Instinct. William Morrow
- ^ 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.
- ^ Nordquist, Richard. “What Is Recursion in English Grammar?” (英語). ThoughtCo. 2019年10月24日閲覧。
- ^ 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時点におけるアーカイブ。.
- ^ Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1
- ^ 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.
- ^ a b Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. pp. 494. ISBN 9781449604424
- ^ “recursion - Google Search”. www.google.com. 2019年10月24日閲覧。
- ^ 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。ISBN 4-87408-414-1。
- ^ 百物語改め「九一三・六物語」「アッカーマン関数の漸化式による説明、数列・カリー化」2015年1月27日
- ^ “Picture of the Day: Fractal Cauliflower” (2012年12月28日). 2020年4月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.”
- ^ “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 2015年9月16日閲覧。
- ^ Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events. Springer. pp. 12
- ^ “Art and Mathematics” (2007年9月5日). 2020年7月5日閲覧。
- ^ ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う？【あらすじと解説】」2022年3月24日
- ^ 数学における 落語『頭山』の世界 自分自身を使って自分を定義する2023年9月8日閲覧。
- ^ 地球にやさしいアルゴリズム 第6回 上手なアルゴリズムの見つけ方2023年9月8日閲覧。
- ^ タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】」2020年5月21日
再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/05/13 04:57 UTC 版)
An の値は次のように再帰的に表せる。 A 0 = 0 {\displaystyle A_{0}=0} A 1 = 2 {\displaystyle A_{1}=2} A 2 = 2 π {\displaystyle A_{2}=2\pi } A n = 2 π n − 2 A n − 2 {\displaystyle A_{n}={\frac {2\pi }{n-2}}A_{n-2}} for n > 2 {\displaystyle n>2} V 0 = 1 {\displaystyle V_{0}=1} V 1 = 2 {\displaystyle V_{1}=2} V n = 2 π n V n − 2 for n > 1 {\displaystyle V_{n}={\frac {2\pi }{n}}V_{n-2}{\text{ for }}n>1}
※この「再帰」の解説は、「単位球面」の解説の一部です。
「再帰」を含む「単位球面」の記事については、「単位球面」の概要を参照ください。
再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/12 16:37 UTC 版)
再帰とは自分自身を関数として使用することで、ラムダ計算では表面上は再帰操作は許されていないように見える。しかし少し工夫することによってラムダ計算でも再帰を実現できる。例として階乗を計算する関数 f(n) を考えてみよう。この関数は再帰的に以下のように定義できる。 f(n) := 1, if n = 0; and n × f(n − 1), if n > 0 ラムダ計算では自分自身を含む関数は定義できない。この問題を解決するためにまず、 f を引数にとり n を引数にとる関数を返すg という関数を考える。 g := λf n. (1, if n = 0; and n × f(n − 1), if n > 0) 関数 g は 1 か n × f(n − 1) を返すような関数を返す。上述の ISZERO や算術、論理記号の定義を用いれば、この関数 g はラムダ式で定義することができる。 しかし、これでは g 自身はまだ再帰的ではない。 g を用いて再帰的な階乗関数を作り出すためには、 g に対して引数 f として渡されている関数が、ある性質を持つ必要がある。すなわち、この f を展開すると関数 g がある一つの引数を伴った形になり、さらにその g への引数は先ほどf として渡された関数に再びなる必要がある。 この性質は言い換えると、 f は g ( f )に展開される必要があるということだ。この g の呼び出しは先ほどの階乗関数に展開され、再帰の段階を一段降りる計算をしている。この展開において、関数 f が再度出現する。そして、この関数 f は再度 g ( f )に展開され、再帰が続いていく。この f = g ( f )となるような関数は、 g の不動点と呼ばれる。そして、この不動点は不動点コンビネータとして知られるものによってラムダ計算で表現することが出来る。この不動点コンビネータは Y と表される -- Yコンビネータ: Y = λg. (λx. g (x x)) (λx. g (x x)) ラムダ計算では、 Y g は g の不動点となる。つまり、 g (Y g) == Y g となる。このもとで、 n の階乗を計算するには単に g (Y g) n を呼び出せばよい。ここで、 n は上述したチャーチ数である。 n = 5 として、評価の例を見てみよう。 (λn.(1, if n = 0; and n·((Y g)(n − 1)), if n > 0)) 51, if 5 = 0; and 5·(g(Y g)(5 − 1)), if 5 > 0 5·(g(Y g) 4) 5·(λn. (1, if n = 0; and n·((Y g)(n − 1)), if n > 0) 4) 5·(1, if 4 = 0; and 4·(g(Y g)(4 − 1)), if 4 > 0) 5·(4·(g(Y g) 3)) 5·(4·(λ n. (1, if n = 0; and n·((Y g)(n− 1)), if n > 0) 3)) 5·(4·(1, if 3 = 0; and 3·(g(Y g)(3 − 1)), if 3 > 0)) 5·(4·(3·(g(Y g) 2))) ... アルゴリズムの構造が再帰的に評価されているのがわかるだろう。再帰的に定義される関数は全て他の適当な関数の不動点となっているため、 Y を用いることで全ての再帰的な関数をラムダ式で表現することができる。たとえば、自然数に対する除算、乗算や比較述語を再帰を用いてよりきれいに定義することができる。
※この「再帰」の解説は、「ラムダ計算」の解説の一部です。
「再帰」を含む「ラムダ計算」の記事については、「ラムダ計算」の概要を参照ください。
再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/06 04:20 UTC 版)
「関数型プログラミング」の記事における「再帰」の解説
詳細は「再帰」を参照 関数型プログラミングの反復処理とループ処理は専ら、関数の再帰を通して行われる。再帰は、無限の項を有限の式で扱えるようにする手法である。再帰で取り沙汰されるスタックオーバーフロー問題は、末尾再帰によるコード最適化で解決されることが多い。再帰は関数型のアルゴリズムの最要点であり、しばしばパターンマッチングやガードと組み合わせて使用される。再帰はデータ構造でも多用され、こちらでは無限の要素を有限の構造で扱えるようにする手法になり、これは再帰データ型とも呼ばれる。
※この「再帰」の解説は、「関数型プログラミング」の解説の一部です。
「再帰」を含む「関数型プログラミング」の記事については、「関数型プログラミング」の概要を参照ください。
再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/10 08:33 UTC 版)
再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。
※この「再帰」の解説は、「ソート」の解説の一部です。
「再帰」を含む「ソート」の記事については、「ソート」の概要を参照ください。
「再帰」の例文・使い方・用例・文例
固有名詞の分類
- >> 「再帰」を含む用語の索引
- 再帰のページへのリンク
