再帰

再帰︵さいき、英: Recursion, Recursive︶とは、ある物事について記述する際に、記述しているもの自体への参照が、その記述中にあらわれることをいう。

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

定義

合わせ鏡の間で撮影すると鏡像が無限に映る。

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

●単純な基底段階 (base case) - 答えを出すのに再帰を使わない、論理展開の終着点。基底は複数あっても構わない。

●再帰段階 (recursive step) - 後続のあらゆる事例を基底段階に帰着させる一連の法則。

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

●その人物の親︵基底段階︶、または

●その人物の親の祖先︵再帰段階︶。

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

●基底1として$Fib(0)=0$$Fib(0)=0$,

●基底2として${\displaystyle Fib($1)=1} $Fib(1)=1$,

●$n>1$$n>1$のあらゆる整数について ${\displaystyle Fib($n)=Fib(n-1)+Fib(n-2)} $Fib(n)=Fib(n-1)+Fib(n-2)$.

多くの数学的公理は、再帰を用いた法則に基づいている。例えば、ペアノの公理による自然数の正式な定義は﹁ゼロは自然数であり、各自然数には後続数があり、これも自然数である﹂と記述されうる。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。

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

言語

言語学者ノーム・チョムスキーらは、言語において適格文の数に上限がなく、適格文の長さにも上限がないことは、自然言語での再帰の結果として説明可能だと論じている。

これは、文章など統語範疇での再帰的定義という観点から理解可能である。文章では、動詞の補語などが別の文章という構造を持つことができる。﹁ドロシーは魔女が危険だと考えている﹂には﹁魔女は危険だ﹂の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に︵非常に大まかだが︶定義することができる。

これは、文章が任意の長さになり得ることも意味する。例えば、英語だと関係代名詞の"that"を使うことによって、

"Dorothy thinks that Toto suspects that Tin Man said that..."

と再帰的に文を継ぎ足すことが可能である。再帰的に定義できうる文章の他にも多くの構造があり、別の品詞に文章を組み込む方法も沢山ある︵例えば修飾語を文章形式にする︶。長い歳月を経て、言語には一般的にこの種の分析で順応性があることが証明されている。

しかし近年、再帰が人類の言語の本来的な性質であるという一般的に受け入れられている思想は、ダニエル・L・エヴェレットによって彼のピダハン語研究に基づく反論が行われている。アンドリュー・ネヴィンズ、デイヴィッド・ペセツキー、シリーン・ロドリゲスがこれに反対する識者達である。いずれの場合でも、文学的な自己言及は数学的・論理的な再帰とは種類が異なると論じられている。

再帰は、構文だけでなく自然言語の意味論においても重要な役割を果たしている。例えば接続詞"and"は、文意に沿った新しい文章を付加できる機能だと解釈することが可能で、名詞句や動詞句などに適用できる。これは、文を繋げる単純な場合について定義したもので、他の接続詞は同様の観点から再帰的に定義することができる。

再帰を使った洒落

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

たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義や自己参照が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。

●再帰については﹁再帰﹂を参照のこと。

これは想定した再帰段階が基底段階へと帰着することなく、無限後退を引き起こすという︵プログラミング失敗例の︶洒落である。この手の最初のジョークは1975-76年に出版されたプログラム言語の教本﹃Let's talk Lisp ﹄と﹃in Software Tools﹄に見られる。これは関数型プログラミングを伝授する一環としての洒落で、上の書籍が出版される前に︵米国の︶プログラミング関連コミュニティで既に広まっていた。

もう一つの冗談が﹁再帰を理解するには、再帰を理解する必要がある﹂というものである。英語版Googleウェブ検索エンジンで"recursion"を検索すると、同サイトでは一番上に"Did you mean: recursion︵再帰って意味だったかな︶"と赤く表示される。

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

数学

シェルピンスキーのギャスケット-フラクタルを形成する三角形の再帰

日本国内の数学では、"Recursion"や"Recursive"に対して再帰の代わりに﹁帰納﹂の訳語をあてた数学用語も幾つか存在する︵帰納的可算集合、帰納言語、帰納的関数など︶。これは下にある﹁自然数の再帰的定義の例﹂でも分かるように、数学における再帰には数学的帰納法と原理的な共通性があるためである。

再帰的定義

詳細は「再帰的定義」を参照

例: 自然数

「閉包」も参照

再帰的に定義された集合の標準例が、自然数である。

0 は$\mathbb {N}$$\mathbb {N}$に含まれる。

仮にnが$\mathbb {N}$$\mathbb {N}$に含まれるなら、n+1は$\mathbb {N}$$\mathbb {N}$に含まれる。

自然数の集合$\mathbb {N}$$\mathbb {N}$とは、上記2つの性質を満たす最小の集合である。

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

例: 証明手続き

もう1つの例は、以下のように帰納または再帰を用いて定義される証明手続き (Proof procedure) の観点から定義される公理体系内のあらゆる﹁証明可能な﹂命題の集合である。

●ある命題が公理であるならば、それは証明可能な命題である。

●ある命題が推論規則によって真に到達可能な命題から導出できるなら、それは証明可能な命題である。

●証明可能な命題の集合は、これらの条件を満たす命題の最小の集合である。

有限分割規則

詳細は「:en:Finite subdivision rule」を参照

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

関数での再帰

詳細は「漸化式」を参照

関数は自身を再帰的に定義する場合がある。とりわけ漸化式が数列を再帰的に定める数式であり、その身近な例が${\displaystyle F($n)=F(n-1)+F(n-2)} $F(n)=F(n-1)+F(n-2)$というフィボナッチ数列である。こうした漸化式による定義が成立する場合、その数式は再帰を用いずに定義された基底値 ︵フィボナッチの場合$F(0)=0$$F(0)=0$ と${\displaystyle F($1)=1} $F(1)=1$︶に帰着できる必要がある。また、漸化式の再帰関係を解いた場合は非再帰的な定義︵一般項︶を得ることが可能である。

有名な再帰関数にアッカーマン関数があるが、これは原始再帰関数よりも早く増大して巨大数を生み出すため、再帰を使わずに一般項を簡単な式で表すことが出来ない点がフィボナッチ数列とは異なる。

再帰的定義を含む証明

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

再帰を使った最適化

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

再帰定理

集合論において、これは再帰的定義がなされた関数が存在することを保証する定理である。集合 Xと、Xの要素 aと、関数f: X→ Xが与えられた場合に、任意の自然数nについて

$F(0)=a$$F(0)=a$
${\displaystyle F(n+1)=f(F($n))} $F(n+1)=f(F(n))$
となるような一意な関数 $F:\mathbb {N} \to X$$F:\mathbb {N} \to X$(where $\mathbb {N}$$\mathbb {N}$が存在する、と同定理は述べている︵ここでの$\mathbb {N}$$\mathbb {N}$は、ゼロを含む自然数の集合を示す︶。

一意性の証明

2つの関数$F:\mathbb {N} \to X$$F:\mathbb {N} \to X$と$G:\mathbb {N} \to X$$G:\mathbb {N} \to X$ を採ると:

$F(0)=a$$F(0)=a$
$G(0)=a$$G(0)=a$
${\displaystyle F(n+1)=f(F($n))} $F(n+1)=f(F(n))$
${\displaystyle G(n+1)=f(G($n))} $G(n+1)=f(G(n))$
ここでaはXの要素である。

すべての自然数nについてF(n) = G(n) であることは数学的帰納法によって証明できる。

基底段階: F(0) = a= G(0) だからn = 0に対して等式が成り立つ。

帰納段階: ある$k\in \mathbb {N}$$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\in \mathbb {N}$$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;
}

生物学

ある大きな部位が複数の小さな自己相似に分岐する構造︵フラクタル︶など、再帰的な過程によって生じたと思われる形状が、植物や動物で時々見られる。野菜のロマネスコがその一例である

芸術

再帰的な人形の例:一組のマトリョーシカ人形(1892年)

ドロステ効果と呼ばれる再帰の視覚形式。このココア箱に描かれた女性の持つ盆の上にあるココア箱には、再び同じ構図の絵が描かれている。ジャン・ミュゼ画(1904)

「ドロステ効果」も参照

ロシアで生まれたマトリョーシカ人形は、再帰という概念の物理的造形例で、日本ではこうした形式を﹁入れ子細工﹂とも呼んでいる。

再帰は、1320年に作られたジョットの三連祭壇画 (Stefaneschi Triptych) 以来、絵画で使用されている。この中央パネルにはステファネスキ枢機卿のひざまずく姿があり、三連祭壇画自体を供物として掲げている。この手法は一般的にドロステ効果と通称されており、紋中紋技法の一例である。

マウリッツ・エッシャーによる1956年の作品 (Print Gallery (M. C. Escher)) は、再帰的な絵を飾った画廊を含む歪んだ都市を描いた版画で、無限に堂々巡りする構図となっている。

日本の文芸作品では、夢野久作の﹃ドグラ・マグラ﹄が再帰的である。本作の序盤に、記憶喪失の青年は﹃ドグラ・マグラ﹄なる小説︵記憶喪失の精神患者が書いたもの︶を見つけることになり、この作中作に綴られている展開や結末をなぞるかのように本作も展開していき混迷の結末へ、という入れ子構造が見られる。

落語﹃頭山﹄の、自分自身の頭に出来た池に身投げしてしまう、というサゲも、再帰的なものとして言及されることがある。

類似する概念

ここではプログラミング手続きの観点から、再帰との主な違いを述べる。

●回帰 - 元々あったオブジェクト︵元の位置や状態︶に戻ってくる事を指す。

対して﹁再帰﹂は元々のオブジェクトではなく、その参照 (計算機科学)にあたる小さいオブジェクトを呼び出す。

●帰納 - 証明手続きの方向性として﹁基底段階の小さなものから段々と大きい︵普遍的な︶もの﹂へと進んでいく。特に数学的帰納法の帰納段階では、任意の自然数$k$$k$に対して${\displaystyle P($k)\to P(k+1)} $P(k)\to P(k+1)$が成り立つ事を示す。

対して﹁再帰﹂のプログラムは﹁大きなものから、段々と小さいもの﹂に進んでいく。${\displaystyle P($k)} $P(k)$を計算するために$k-1$$k-1$の参照オブジェクトを呼び出し、この$k$$k$が基底段階に達するまで処理を繰り返し行う。

関連項目

言語

• 再帰動詞
• 左再帰
• 自己言及

数学

• 再帰理論
• 反復関数系
• 漸化式
• 数学的帰納法

計算機科学

• ネスティング
• 不動点コンビネータ
• 無限ループ#無限再帰
• 末尾再帰
• リエントラント

その他

• ドロステ効果/紋中紋/入れ子
• 合わせ鏡/ビデオフィードバック
• ハノイの塔 -解の操作手順が再帰的構造のパズル

外部リンク

• 「再帰処理」を使って幾何学模様を描いてみよう - マイナビ、関数プログラムを含めた解説
• Recursion - tutorial by Alan Gauld
• Zip Files All The Way Down