再帰 (さいき、英 : Recursion, Recursive )とは、ある物事について記述する際に、記述しているもの自体への参照 が[ 注釈 1] 、その記述中にあらわれることをいう。
再帰は言語学 から論理学 に至る様々な分野で使用されている。最も一般的な適用は数学 と計算機科学 で、定義されている関数 がそれ自身の定義の中で参照利用されている場合を言う。
定義
合わせ鏡 の間で撮影すると鏡像が無限に映る。
平行な合わせ鏡 の間に物体を置くと、その像が鏡の中に無限に映し出される。このように、あるものが部分的にそれ自身で構成されていたり、それ自身によって定義されている時に、それを「再帰的(Recursive)」だという[ 1] [ 2] 。論理的思考の重要な特質のひとつであり、数学では漸化式 や数学的帰納法 が再帰的構造を持っている[ 1] 。計算機科学だと、オブジェクト やメソッド のクラス が、以下2つの項目で定義できる場合に再帰的構造だと言える。
単純な基底段階 (base case ) - 答えを出すのに再帰を使わない、論理展開の終着点。基底は複数あっても構わない。
再帰段階 (recursive step ) - 後続のあらゆる事例を基底段階に帰着させる一連の法則。
例えば、これは人間の祖先の再帰的定義である。ある人物の祖先は次のいずれかになる。
その人物の親(基底段階)、または
その人物の親の祖先(再帰段階)。
フィボナッチ数列 は、再帰を用いた古典的な数式例である。
基底1として
F
i
b
(
0
)
=
0
{\displaystyle Fib(0)=0}
,
基底2として
F
i
b
(
1
)
=
1
{\displaystyle Fib(1)=1}
,
n
>
1
{\displaystyle n>1}
のあらゆる整数 について
F
i
b
(
n
)
=
F
i
b
(
n
− − -->
1
)
+
F
i
b
(
n
− − -->
2
)
{\displaystyle Fib(n)=Fib(n-1)+Fib(n-2)}
.
多くの数学的公理 は、再帰を用いた法則に基づいている。例えば、ペアノの公理 による自然数の正式な定義は「ゼロは自然数であり、各自然数には後続数があり、これも自然数である」と記述されうる[ 3] 。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。
他にも再帰を用いて定義されている数学的対象としては、関数の漸化式 、集合のカントール集合 、フラクタル 分野、プログラミング言語における階乗 、などがある。
言語
言語学者ノーム・チョムスキー らは、言語において適格文 の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている[ 4] [ 5] 。
これは、文章など統語範疇 での再帰的定義という観点から理解可能である。文章では、動詞の補語 などが別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に(非常に大まかだが)定義することができる。
これは、文章が任意の長さになり得ることも意味する。例えば、英語だと関係代名詞 の"that"を使うことによって、
"Dorothy thinks that Toto suspects that Tin Man said that..."
と再帰的に文を継ぎ足すことが可能である。再帰的に定義できうる文章の他にも多くの構造があり、別の品詞に文章を組み込む方法も沢山ある(例えば修飾語 を文章形式にする)。長い歳月を経て、言語には一般的にこの種の分析で順応性があることが証明されている[ 6] 。
しかし近年、再帰が人類の言語の本来的な性質であるという一般的に受け入れられている思想は、ダニエル・L・エヴェレット によって彼のピダハン語 研究に基づく反論が行われている。アンドリュー・ネヴィンズ、デイヴィッド・ペセツキー、シリーン・ロドリゲスがこれに反対する識者達である[ 7] 。いずれの場合でも、文学的な自己言及 は数学的・論理的な再帰とは種類が異なると論じられている[ 8] 。
再帰は、構文だけでなく自然言語の意味論 においても重要な役割を果たしている。例えば接続詞 "and"は、文意に沿った新しい文章を付加できる機能だと解釈することが可能で、名詞句や動詞句などに適用できる。これは、文を繋げる単純な場合について定義したもので、他の接続詞は同様の観点から再帰的に定義することができる[ 9] 。
再帰を使った洒落
再帰的なウィキペディアのページ。
たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義 や自己参照 が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。
これは想定した再帰段階が基底段階へと帰着することなく、無限後退 を引き起こすという(プログラミング失敗例の)洒落である。この手の最初のジョークは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"を表す。
数学
シェルピンスキーのギャスケット -フラクタル を形成する三角形の再帰
日本国内の数学では、"Recursion"や"Recursive"に対して再帰の代わりに「帰納」の訳語をあてた数学用語も幾つか存在する(帰納的可算集合 、帰納言語 、帰納的関数 など)。これは下にある「自然数の再帰的定義の例」でも分かるように、数学における再帰には数学的帰納法 と原理的な共通性があるためである。
再帰的定義
例: 自然数
再帰的に定義された集合の標準例が、自然数 である。
0 は
N
{\displaystyle \mathbb {N} }
に含まれる。
仮にn が
N
{\displaystyle \mathbb {N} }
に含まれるなら、n +1は
N
{\displaystyle \mathbb {N} }
に含まれる。
自然数の集合
N
{\displaystyle \mathbb {N} }
とは、上記2つの性質を満たす最小の集合である[ 注釈 3] 。
数理論理学において、ペアノの公理 とはドイツの数学者リヒャルト・デーデキント とイタリアの数学者ジュゼッペ・ペアノ によって19世紀に提示された自然数の公理である。ペアノの公理は、再帰的な後者関数 と再帰関数としての加算・乗算を参照して自然数を定義している。
例: 証明手続き
もう1つの例は、以下のように帰納または再帰を用いて定義される証明手続き (Proof procedure ) の観点から定義される公理体系 内のあらゆる「証明可能な」命題の集合である。
ある命題が公理であるならば、それは証明可能な命題である。
ある命題が推論規則によって真に到達可能な命題から導出できるなら、それは証明可能な命題である。
証明可能な命題の集合は、これらの条件を満たす命題の最小の集合である。
有限分割規則
有限分割規則は再帰の幾何学的形式で、これはフラクタル模様を作図するのに使用される。分割規則は、有限に多くのラベル でラベル付けされた多角形の集まりを起点として、各多角形は最初の多角形ラベルにのみ依存する方法で、より小さなラベル付き多角形に分割される。この工程は繰り返し行うことができる。カントール集合 を作るための標準的な「3等分の中央部を除去する」技法が、分割規則の例である。
関数での再帰
関数は自身を再帰的に定義する場合がある。とりわけ漸化式が数列を再帰的に定める数式であり、その身近な例が
F
(
n
)
=
F
(
n
− − -->
1
)
+
F
(
n
− − -->
2
)
{\displaystyle F(n)=F(n-1)+F(n-2)}
というフィボナッチ数列 である。こうした漸化式による定義が成立する場合、その数式は再帰を用いずに定義された基底値 (フィボナッチの場合
F
(
0
)
=
0
{\displaystyle F(0)=0}
と
F
(
1
)
=
1
{\displaystyle F(1)=1}
)に帰着できる必要がある。また、漸化式の再帰関係を解いた場合は非再帰的な定義(一般項)を得ることが可能である[ 注釈 4] 。
有名な再帰関数にアッカーマン関数 があるが、これは原始再帰関数 よりも早く増大して巨大数 を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない[ 13] 点がフィボナッチ数列とは異なる。
再帰的定義を含む証明
前節のような、再帰的定義がされた集合や関数に対して複数場合分けによる証明の標準的な手法を適用すると、構造的帰納法 が得られる。これは数理論理学 とコンピュータサイエンスで証明を導出するのに広く使用されている数学的帰納法 の強力な一般化である。
再帰を使った最適化
動的計画法 は、多周期ないし多段階の最適化問題 を再帰形式で再記述する数理最適化 へのアプローチ手法である。動的計画法の主な成果がベルマン方程式 で、これは最適化問題の直近時(直近段階)での値を、その次回時刻(次段階)における値の観点から記述するものである。
再帰定理
集合論 において、これは再帰的定義がなされた関数が存在することを保証する定理である。集合 X と、X の要素 a と、関数f : X → X が与えられた場合に、任意の自然数n について
F
(
0
)
=
a
{\displaystyle F(0)=a}
F
(
n
+
1
)
=
f
(
F
(
n
)
)
{\displaystyle F(n+1)=f(F(n))}
となるような一意な関数
F
:
N
→ → -->
X
{\displaystyle F:\mathbb {N} \to X}
(where
N
{\displaystyle \mathbb {N} }
が存在する、と同定理は述べている(ここでの
N
{\displaystyle \mathbb {N} }
は、ゼロを含む自然数の集合を示す)。
一意性の証明
2つの関数
F
:
N
→ → -->
X
{\displaystyle F:\mathbb {N} \to X}
と
G
:
N
→ → -->
X
{\displaystyle G:\mathbb {N} \to X}
を採ると:
F
(
0
)
=
a
{\displaystyle F(0)=a}
G
(
0
)
=
a
{\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 に対して等式が成り立つ。
帰納段階 : ある
k
∈ ∈ -->
N
{\displaystyle k\in \mathbb {N} }
. についてF (k ) = G (k ) と仮定すると、F (k + 1) = f (F (k )) = f (G (k )) = G (k + 1) である。
したがってF (k ) = G (k ) は F (k + 1) = G (k + 1) を含んでいる。
帰納法により、全ての
n
∈ ∈ -->
N
{\displaystyle n\in \mathbb {N} }
についてF (n ) = G (n ) である。
計算機科学
単純化の一般的な方法は、問題を同じ種類の小問に分割することである。コンピュータプログラミングの技法としてこれは分割統治法 と呼ばれ、多くの重要なアルゴリズム設計の鍵となる。分割統治法は、問題解決へのトップダウン型アプローチとして機能し、そこでは問題がより小さなインスタンス を解決することにより解決される。反対のアプローチ手法は動的計画法 である。こちらはボトムアップ型アプローチとして機能し、目的の規模に達するまでより大きなインスタンスを解決することによって問題が解決される。
プログラミングの観点では、nを表現するのにn-1という参照を持ち出してくるものを「再帰」という。再帰の古典的な例としては、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)!。再帰呼出し */
}
この関数では、掛け算のため入力自身より小さな(n-1)という参照を再帰的に呼び出し、再帰呼び出しの結果にnを掛ける処理を、階乗の数学的定義と同じく基底段階の値に達するまで実行する。
アルゴリズム における再帰の使用には、長所も短所もある。主な長所は、一般に命令の単純さである。主な短所は、自身を呼び出す手法なので引数が再帰終了条件を満たさない状況を避けるよう値の変化に注意する必要があること。また、再帰アルゴリズムのメモリ使用量が著しく激増して負荷がかかるため、大規模なインスタンスを扱うには非実用的な点である。
再帰呼出し
手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム(再帰的アルゴリズム)を記述するのに適している。
複数の手続き/関数が互いに相手を呼ぶ場合も、広い意味での再帰呼出し(相互再帰 )である。C言語での例:
void a () {
b ();
}
void b () {
a ();
}
処理を中断・終了する基底条件が必ず1つは必要で、その部分が誤っていると、無限に関数を呼び出し続けることがある(暴走 )。無限再帰に陥ると、スタックオーバーフロー によりプログラムが異常終了したり、システムが停止したりする原因となる。
再帰的データ構造
連結リスト や木構造 は、要素(ノード)の型の中にその要素型自身への参照(自己参照 )が存在するようなデータ型を用いて実現される。これは再帰的データ構造(再帰データ型 )である。再帰的データ構造の探索には、再帰呼び出しを使うことが多い。
下記は Java での例。Tree のクラス定義の中で Tree を使用している。
class Tree {
Tree [] children ;
}
生物学
ある大きな部位が複数の小さな自己相似 に分岐する構造(フラクタル )など、再帰的な過程によって生じたと思われる形状が、植物や動物で時々見られる。野菜のロマネスコ がその一例である[ 14]
芸術
再帰的な人形の例:一組のマトリョーシカ人形 (1892年)
ドロステ効果 と呼ばれる再帰の視覚形式。このココア 箱に描かれた女性の持つ盆の上にあるココア箱には、再び同じ構図の絵が描かれている。ジャン・ミュゼ画(1904)
ロシアで生まれたマトリョーシカ人形 は、再帰という概念の物理的造形例で[ 15] 、日本ではこうした形式を「入れ子 細工」とも呼んでいる。
再帰は、1320年に作られたジョット の三連祭壇画 (Stefaneschi Triptych ) 以来、絵画で使用されている。この中央パネルにはステファネスキ枢機卿のひざまずく姿があり、三連祭壇画自体を供物として掲げている[ 16] [ 17] 。この手法は一般的にドロステ効果 と通称されており、紋中紋 技法の一例である。
マウリッツ・エッシャー による1956年の作品 (Print Gallery (M. C. Escher) ) は、再帰的な絵を飾った画廊を含む歪んだ都市を描いた版画で、無限に堂々巡りする構図となっている[ 18] 。
日本の文芸作品では、夢野久作 の『ドグラ・マグラ 』が再帰的である。本作の序盤に、記憶喪失の青年は『ドグラ・マグラ』なる小説(記憶喪失の精神患者が書いたもの)を見つけることになり、この作中作に綴られている展開や結末をなぞるかのように本作も展開していき混迷の結末へ、という入れ子構造が見られる[ 19] 。
落語『頭山 』の、自分自身の頭に出来た池に身投げしてしまう、というサゲも、再帰的なものとして言及されることがある。[ 20] [ 21]
類似する概念
ここではプログラミング手続きの観点から、再帰との主な違いを述べる。
回帰 - 元々あったオブジェクト(元の位置や状態)に戻ってくる事を指す。
対して「再帰」は元々のオブジェクトではなく、その参照 (計算機科学) にあたる小さいオブジェクトを呼び出す。
帰納 - 証明手続きの方向性として「基底段階の小さなものから段々と大きい(普遍的な)もの」へと進んでいく。特に数学的帰納法 の帰納段階では、任意の自然数
k
{\displaystyle k}
に対して
P
(
k
)
→ → -->
P
(
k
+
1
)
{\displaystyle P(k)\to P(k+1)}
が成り立つ事を示す。
対して「再帰」のプログラムは「大きなものから、段々と小さいもの」に進んでいく[ 22] 。
P
(
k
)
{\displaystyle P(k)}
を計算するために
k
− − -->
1
{\displaystyle k-1}
の参照オブジェクトを呼び出し、この
k
{\displaystyle k}
が基底段階に達するまで処理を繰り返し行う。
関連項目
脚注
注釈
^ 記述している対象と同義な性質・情報を有する(幾何学でいう相似 関係の)主に小さい事象を参照と呼ぶ。記述している対象と完全に同一なもの(幾何学でいう合同 図形)は参照に含めない。
^ 顛末まで解説すると、"recursion"の文字列には青のページリンクが張られており、このリンク先が"recursion"を再検索(自己参照)した結果ページという洒落。日本語版Google検索でも、「再帰」を検索すると同様の仕組みが「もしかして:再帰」で見られる。
^ なお、自然数に0を含めるか否かは扱う数学分野によって異なることがある(例えば数論 や解析学 では一般に0を含めない)。詳細は自然数 を参照。
^ フィボナッチ数列の非再帰的な一般項は、次の通り[ 12] :
F
n
=
1
5
{
(
1
+
5
2
)
n
− − -->
(
1
− − -->
5
2
)
n
}
{\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}}
出典
^ 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時点におけるアーカイブ。. 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 .
^ Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic . Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1 . https://books.google.com/books?id=R70M4zsVgREC&pg=PA110
^ 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 . https://books.google.com/books?id=kuwhTxCVovQC&q=recursion+joke
^ “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 ” (28 December 2012). 19 April 2020 閲覧。
^ “Recursion ”. 24 September 2015 閲覧。 “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. 16 September 2015 閲覧。
^ Svozil, Karl (2018). Physical (A)Causality: Determinism, Randomness and Uncaused Events . Springer. pp. 12. https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12
^ “Art and Mathematics ” (5 September 2007). 5 July 2020 閲覧。
^ ホンシェルジュ「5分でわかる『ドグラ・マグラ』読んだら気が狂う?【あらすじと解説】 」2022年3月24日
^ 数学における 落語『頭山』の世界 自分自身を使って自分を定義する 2023年9月8日 閲覧。
^ 地球にやさしいアルゴリズム 第6回 上手なアルゴリズムの見つけ方 2023年9月8日 閲覧。
^ タクマ「【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】 」2020年5月21日
外部リンク
ウィキメディア・コモンズには、
再帰 に関連するカテゴリがあります。