再帰さいき

再帰さいき（さいき、英えい: Recursion, Recursive）とは、ある物事ものごとについて記述きじゅつする際さいに、記述きじゅつしているもの自体じたいへの参照さんしょうが^{[注釈ちゅうしゃく 1]}、その記述きじゅつ中ちゅうにあらわれることをいう。

再帰さいきは言語げんご学がくから論理ろんり学がくに至いたる様々さまざまな分野ぶんやで使用しようされている。最もっとも一般いっぱん的てきな適用てきようは数学すうがくと計算けいさん機き科学かがくで、定義ていぎされている関数かんすうがそれ自身じしんの定義ていぎの中なかで参照さんしょう利用りようされている場合ばあいを言いう。

定義ていぎ

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

単純たんじゅんな基底きてい段階だんかい (base case) - 答こたえを出だすのに再帰さいきを使つかわない、論理ろんり展開てんかいの終着しゅうちゃく点てん。基底きていは複数ふくすうあっても構かまわない。
再帰さいき段階だんかい (recursive step) - 後続こうぞくのあらゆる事例じれいを基底きてい段階だんかいに帰着きちゃくさせる一連いちれんの法則ほうそく。

例たとえば、これは人間にんげんの祖先そせんの再帰さいき的てき定義ていぎである。ある人物じんぶつの祖先そせんは次つぎのいずれかになる。

その人物じんぶつの親おや（基底きてい段階だんかい）、または
その人物じんぶつの親おやの祖先そせん（再帰さいき段階だんかい）。

フィボナッチ数列すうれつは、再帰さいきを用もちいた古典こてん的てきな数式すうしき例れいである。

基底きてい1として $Fib(0)=0$ ,
基底きてい2として $Fib(1)=1$ ,
$n>1$ のあらゆる整数せいすうについて $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]。

再帰さいきを使つかった洒落しゃれ

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

再帰さいきについては「再帰さいき」を参照さんしょうのこと^[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"を表あらわす。

数学すうがく

日本にっぽん国内こくないの数学すうがくでは、"Recursion"や"Recursive"に対たいして再帰さいきの代かわりに「帰納きのう」の訳語やくごをあてた数学すうがく用語ようごも幾いくつか存在そんざいする（帰納的きのうてき可算かさん集合しゅうごう、帰納きのう言語げんご、帰納的きのうてき関数かんすうなど）。これは下したにある「自然しぜん数すうの再帰さいき的てき定義ていぎの例れい」でも分わかるように、数学すうがくにおける再帰さいきには数学すうがく的てき帰納きのう法ほうと原理げんり的てきな共通きょうつう性せいがあるためである。

再帰さいき的てき定義ていぎ

詳細しょうさいは「再帰さいき的てき定義ていぎ」を参照さんしょう

例れい: 自然しぜん数すう

「閉包へいほう」も参照さんしょう

再帰さいき的てきに定義ていぎされた集合しゅうごうの標準ひょうじゅん例れいが、自然しぜん数すうである。

0 は

\mathbb {N}

に含ふくまれる。

仮かりにnが

\mathbb {N}

に含ふくまれるなら、n+1は

\mathbb {N}

に含ふくまれる。

自然しぜん数すうの集合しゅうごう

\mathbb {N}

とは、上記じょうき2つの性質せいしつを満みたす最小さいしょうの集合しゅうごうである^{[注釈ちゅうしゃく 3]}。

数理すうり論理ろんり学がくにおいて、ペアノの公理こうりとはドイツの数学すうがく者しゃリヒャルト・デーデキントとイタリアの数学すうがく者しゃジュゼッペ・ペアノによって19世紀せいきに提示ていじされた自然しぜん数すうの公理こうりである。ペアノの公理こうりは、再帰さいき的てきな後者こうしゃ関数かんすうと再帰さいき関数かんすうとしての加算かさん・乗算じょうざんを参照さんしょうして自然しぜん数すうを定義ていぎしている。

例れい: 証明しょうめい手続てつづき

もう1つの例れいは、以下いかのように帰納きのうまたは再帰さいきを用もちいて定義ていぎされる証明しょうめい手続てつづき (Proof procedure) の観点かんてんから定義ていぎされる公理こうり体系たいけい内うちのあらゆる「証明しょうめい可能かのうな」命題めいだいの集合しゅうごうである。

ある命題めいだいが公理こうりであるならば、それは証明しょうめい可能かのうな命題めいだいである。
ある命題めいだいが推論すいろん規則きそくによって真しんに到達とうたつ可能かのうな命題めいだいから導出どうしゅつできるなら、それは証明しょうめい可能かのうな命題めいだいである。
証明しょうめい可能かのうな命題めいだいの集合しゅうごうは、これらの条件じょうけんを満みたす命題めいだいの最小さいしょうの集合しゅうごうである。

有限ゆうげん分割ぶんかつ規則きそく

詳細しょうさいは「:en:Finite subdivision rule」を参照さんしょう

有限ゆうげん分割ぶんかつ規則きそくは再帰さいきの幾何きか学がく的てき形式けいしきで、これはフラクタル模様もようを作図さくずするのに使用しようされる。分割ぶんかつ規則きそくは、有限ゆうげんに多おおくのラベルでラベル付らべるつけされた多角たかく形がたの集あつまりを起点きてんとして、各かく多角たかく形がたは最初さいしょの多角たかく形がたラベルにのみ依存いぞんする方法ほうほうで、より小ちいさなラベル付つき多角たかく形がたに分割ぶんかつされる。この工程こうていは繰くり返かえし行おこなうことができる。カントール集合しゅうごうを作つくるための標準ひょうじゅん的てきな「3等分とうぶんの中央ちゅうおう部ぶを除去じょきょする」技法ぎほうが、分割ぶんかつ規則きそくの例れいである。

関数かんすうでの再帰さいき

詳細しょうさいは「漸やや化か式しき」を参照さんしょう

関数かんすうは自身じしんを再帰さいき的てきに定義ていぎする場合ばあいがある。とりわけ漸すすむ化か式しきが数列すうれつを再帰さいき的てきに定さだめる数式すうしきであり、その身近みぢかな例れいが $F(n)=F(n-1)+F(n-2)$ というフィボナッチ数列すうれつである。こうした漸すすむ化か式しきによる定義ていぎが成立せいりつする場合ばあい、その数式すうしきは再帰さいきを用もちいずに定義ていぎされた基底きてい値ち（フィボナッチの場合ばあい $F(0)=0$ と $F(1)=1$ ）に帰着きちゃくできる必要ひつようがある。また、漸やや化か式しきの再帰さいき関係かんけいを解といた場合ばあいは非ひ再帰さいき的てきな定義ていぎ（一般いっぱん項こう）を得えることが可能かのうである^{[注釈ちゅうしゃく 4]}。

有名ゆうめいな再帰さいき関数かんすうにアッカーマン関数かんすうがあるが、これは原始げんし再帰さいき関数かんすうよりも早はやく増大ぞうだいして巨きょ大数たいすうを生うみ出だすため、再帰さいきを使つかわずに一般いっぱん項こうを簡単かんたんな式しきで表あらわすことが出来できない^[13]点てんがフィボナッチ数列すうれつとは異ことなる。

再帰さいき的てき定義ていぎを含ふくむ証明しょうめい

前節ぜんせつのような、再帰さいき的てき定義ていぎがされた集合しゅうごうや関数かんすうに対たいして複数ふくすう場合ばあい分わけによる証明しょうめいの標準ひょうじゅん的てきな手法しゅほうを適用てきようすると、構造こうぞう的てき帰納きのう法ほうが得えられる。これは数理すうり論ろん理学りがくとコンピュータサイエンスで証明しょうめいを導出どうしゅつするのに広ひろく使用しようされている数学すうがく的てき帰納きのう法ほうの強力きょうりょくな一般いっぱん化かである。

再帰さいきを使つかった最適さいてき化か

動的どうてき計画けいかく法ほうは、多た周期しゅうきないし多た段階だんかいの最適さいてき化か問題もんだいを再帰さいき形式けいしきで再さい記述きじゅつする数理すうり最適さいてき化かへのアプローチ手法しゅほうである。動的どうてき計画けいかく法ほうの主おもな成果せいかがベルマン方程式ほうていしきで、これは最適さいてき化か問題もんだいの直近ちょっきん時じ（直近ちょっきん段階だんかい）での値ねを、その次回じかい時刻じこく（次段じだん階かい）における値ねの観点かんてんから記述きじゅつするものである。

再帰さいき定理ていり

集合しゅうごう論ろんにおいて、これは再帰さいき的てき定義ていぎがなされた関数かんすうが存在そんざいすることを保証ほしょうする定理ていりである。集合しゅうごう $X$ と、 $X$ の要素ようそ $a$ と、関数かんすう $f : X \to X$ が与あたえられた場合ばあいに、任意にんいの自然しぜん数すう $n$ について

F(0)=a

F(n+1)=f(F(n))

となるような一意いちいな関数かんすう $F:\mathbb {N} \to X$ (where $\mathbb {N}$ が存在そんざいする、と同どう定理ていりは述のべている（ここでの $\mathbb {N}$ は、ゼロを含ふくむ自然しぜん数すうの集合しゅうごうを示しめす）。

一意いちい性せいの証明しょうめい

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

F(0)=a

G(0)=a

F(n+1)=f(F(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}

.について

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}$ について $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]

芸術げいじゅつ

「ドロステ効果こうか」も参照さんしょう

ロシアで生うまれたマトリョーシカ人形にんぎょうは、再帰さいきという概念がいねんの物理ぶつり的てき造形ぞうけい例れいで^[15]、日本にっぽんではこうした形式けいしきを「入いれ子こ細工ざいく」とも呼よんでいる。

再帰さいきは、1320年ねんに作つくられたジョットの三さん連れん祭壇さいだん画が (Stefaneschi Triptych) 以来いらい、絵画かいがで使用しようされている。この中央ちゅうおうパネルにはステファネスキ枢機卿すうききょうのひざまずく姿すがたがあり、三さん連れん祭壇さいだん画が自体じたいを供物くもつとして掲かかげている^[16]^[17]。この手法しゅほうは一般いっぱん的てきにドロステ効果こうかと通称つうしょうされており、紋もん中ちゅう紋もん技法ぎほうの一いち例れいである。

マウリッツ・エッシャーによる1956年ねんの作品さくひん (Print Gallery (M. C. Escher)) は、再帰さいき的てきな絵えを飾かざった画廊がろうを含ふくむ歪いがんだ都市としを描えがいた版画はんがで、無限むげんに堂々巡どうどうめぐりする構図こうずとなっている^[18]。

日本にっぽんの文芸ぶんげい作品さくひんでは、夢野ゆめの久作きゅうさくの『ドグラ・マグラ』が再帰さいき的てきである。本ほん作さくの序盤じょばんに、記憶きおく喪失そうしつの青年せいねんは『ドグラ・マグラ』なる小説しょうせつ（記憶きおく喪失そうしつの精神せいしん患者かんじゃが書かいたもの）を見みつけることになり、この作中さくちゅう作さくに綴つづられている展開てんかいや結末けつまつをなぞるかのように本ほん作さくも展開てんかいしていき混迷こんめいの結末けつまつへ、という入いれ子こ構造こうぞうが見みられる^[19]。

落語らくご『頭山とうやま』の、自分じぶん自身じしんの頭あたまに出来できた池いけに身投みなげしてしまう、というサゲも、再帰さいき的てきなものとして言及げんきゅうされることがある。^[20]^[21]

類似るいじする概念がいねん

ここではプログラミング手続てつづきの観点かんてんから、再帰さいきとの主おもな違ちがいを述のべる。

回帰かいき - 元々もともとあったオブジェクト（元もとの位置いちや状態じょうたい）に戻もどってくる事ことを指さす。

対たいして「再帰さいき」は元々もともとのオブジェクトではなく、その参照さんしょう (計算けいさん機き科学かがく)にあたる小ちいさいオブジェクトを呼よび出だす。

帰納きのう - 証明しょうめい手続てつづきの方向ほうこう性せいとして「基底きてい段階だんかいの小ちいさなものから段々だんだんと大おおきい（普遍ふへん的てきな）もの」へと進すすんでいく。特とくに数学すうがく的てき帰納きのう法ほうの帰納きのう段階だんかいでは、任意にんいの自然しぜん数すう $k$ に対たいして $P(k)\to P(k+1)$ が成なり立たつ事ことを示しめす。

対たいして「再帰さいき」のプログラムは「大おおきなものから、段々だんだんと小ちいさいもの」に進すすんでいく^[22]。

P(k)

を計算けいさんするために

k-1

の参照さんしょうオブジェクトを呼よび出だし、この

k

が基底きてい段階だんかいに達たっするまで処理しょりを繰くり返かえし行おこなう。

脚注きゃくちゅう

[脚注きゃくちゅうの使つかい方かた]

注釈ちゅうしゃく

^ 記述きじゅつしている対象たいしょうと同義どうぎな性質せいしつ・情報じょうほうを有ゆうする（幾何きか学がくでいう相似そうじ関係かんけいの）主おもに小ちいさい事象じしょうを参照さんしょうと呼よぶ。記述きじゅつしている対象たいしょうと完全かんぜんに同一どういつなもの（幾何きか学がくでいう合同ごうどう図形ずけい）は参照さんしょうに含ふくめない。
^ 顛末てんまつまで解説かいせつすると、"recursion"の文字もじ列れつには青あおのページリンクが張はられており、このリンク先さきが"recursion"を再さい検索けんさく（自己じこ参照さんしょう）した結果けっかページという洒落しゃれ。日本語にほんご版ばんGoogle検索けんさくでも、「再帰さいき」を検索けんさくすると同様どうようの仕組しくみが「もしかして：再帰さいき」で見みられる。
^ なお、自然しぜん数すうに0を含ふくめるか否ひかは扱あつかう数学すうがく分野ぶんやによって異ことなることがある（例たとえば数かず論ろんや解析かいせき学がくでは一般いっぱんに0を含ふくめない）。詳細しょうさいは自然しぜん数すうを参照さんしょう。
^ フィボナッチ数列すうれつの非ひ再帰さいき的てきな一般いっぱん項こうは、次つぎの通とおり^[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\}$

出典しゅってん

^ ^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” (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
^ “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日にち

外部がいぶリンク

「再帰さいき処理しょり」を使つかって幾何きか学がく模様もようを描えがいてみよう - マイナビ、関数かんすうプログラムを含ふくめた解説かいせつ
Recursion - tutorial by Alan Gauld
Zip Files All The Way Down

[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” (28 December 2012). 19 April 2020閲覧えつらん。

[19] “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.”

[20] “Giotto di Bondone and assistants: Stefaneschi triptych”. The Vatican. 16 September 2015閲覧えつらん。

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

[22] “Art and Mathematics” (5 September 2007). 5 July 2020閲覧えつらん。

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

[24] 数学すうがくにおける落語らくご『頭山とうやま』の世界せかい自分じぶん自身じしんを使つかって自分じぶんを定義ていぎする2023年ねん9月がつ8日にち閲覧えつらん。

[25] 地球ちきゅうにやさしいアルゴリズム第だい6回かい上手じょうずなアルゴリズムの見みつけ方かた2023年ねん9月がつ8日にち閲覧えつらん。

[26] タクマ「【再帰さいき的てきプログラム】再帰さいき・帰納きのうの違ちがいを解説かいせつ【階かい乗じょう0!が1の理由りゆう】」2020年ねん5月がつ21日にち

[注釈ちゅうしゃく 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[注釈ちゅうしゃく 2]

[注釈ちゅうしゃく 3]

[注釈ちゅうしゃく 4]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[12]

表ひょう話はなし編へん歴れきフラクタル
特徴とくちょう	フラクタル次元じげん Assouad（英語えいご版ばん） Box-counting（英語えいご版ばん） Correlation（英語えいご版ばん）ハウスドルフ Packing（英語えいご版ばん）位相いそう再帰さいき（英語えいご版ばん）自己じこ相似そうじ自己じこ相似そうじ過程かていスケール不変ふへん性せい
反復はんぷく関数かんすう系けい	バーンズリーのシダカントール集合しゅうごうドラゴン曲線きょくせんレヴィC曲線きょくせんコッホ雪片せっぺんメンガーのスポンジシェルピンスキーのカーペットシェルピンスキーの三角形さんかっけい空間くうかん充填じゅうてん曲線きょくせん T-square（英語えいご版ばん）
ストレンジアトラクター	多重たじゅうフラクタル系けい（英語えいご版ばん）
L-system	空間くうかん充填じゅうてん曲線きょくせん
Escape-time fractals	バーニングシップ・フラクタルジュリア集合しゅうごう充填じゅうてんリアプノフ・フラクタルマンデルブロ集合しゅうごうニュートン・フラクタル（英語えいご版ばん）
確かく率りつ的てきフラクタル	ブラウン運動うんどう非ひ整数せいすうブラウン運動うんどうブラウンの木き（英語えいご版ばん）拡散かくさん律りつ速そく凝集ぎょうしゅうフラクタル地形ちけい Lévy flight（英語えいご版ばん）パーコレーション理論りろん（英語えいご版ばん） Self-avoiding walk（英語えいご版ばん）
人物じんぶつ	ゲオルク・カントールフェリックス・ハウスドルフガストン・ジュリアヘルゲ・フォン・コッホポール・レヴィアレクサンドル・リャプノフブノワ・マンデルブロルイス・フライ・リチャードソンヴァツワフ・シェルピニスキ
その他た	"How Long Is the Coast of Britain?（英語えいご版ばん）" 海岸かいがん線せんのパラドックス List of fractals by Hausdorff dimension（英語えいご版ばん） The Beauty of Fractals（英語えいご版ばん） (1986 book)
カテゴリ

表ひょう話はなし編へん歴れき数理すうり論ろん理学りがく
一般いっぱん	形式けいしき言語げんご構成こうせい規則きそく形式けいしき体系たいけい演繹えんえきシステム（英語えいご版ばん）形式けいしき的てき証明しょうめい形式けいしき意味いみ論ろん論理ろんり式しき集合しゅうごう元もとクラス古典こてん論理ろんり公理こうり自然しぜん演繹えんえき推論すいろん規則きそく関係かんけい定理ていり論理ろんり的てき帰結きけつ公理系こうりけい型かた理論りろん記号きごう（英語えいご版ばん）統語とうご論ろん（英語えいご版ばん）理論りろん（英語えいご版ばん）
Traditional logic（英語えいご版ばん）	命題めいだい推論すいろん論証ろんしょう妥当だとう性せい Cogency 三段論法さんだんろんぽう Square of opposition（英語えいご版ばん）ベン図べんず
命題めいだい論理ろんり・ブール論理ろんり	ブール関数かんすう命題めいだい論理ろんり命題めいだい論理ろんり式しき（英語えいご版ばん）論理ろんり演算えんざん真理しんり値ち表ひょう多値たち論理ろんり
述語じゅつご論理ろんり	一いち階かい量りょう化か子こ述語じゅつご（英語えいご版ばん）二に階かい Monadic predicate calculus（英語えいご版ばん）
素朴そぼく集合しゅうごう論ろん	集合しゅうごう空そら集合しゅうごう元もと数かぞえ上あげ外延がいえん有限ゆうげん集合しゅうごう無限むげん集合しゅうごう部分ぶぶん集合しゅうごう冪べき集合しゅうごう可算かさん集合しゅうごう非ひ可算かさん集合しゅうごう帰納的きのうてき集合しゅうごう定義ていぎ域いき終おわり域いき像ぞう写像しゃぞう関数かんすう関係かんけい順序じゅんじょ対たい
集合しゅうごう論ろん	数学すうがく基礎きそ論ろんツェルメロ＝フレンケル集合しゅうごう論ろん選択せんたく公理こうり一般いっぱん集合しゅうごう論ろん（英語えいご版ばん） Kripke–Platek 集合しゅうごう論ろん（英語えいご版ばん）フォン・ノイマン＝ベルナイス＝ゲーデル集合しゅうごう論ろん（英語えいご版ばん）モース-ケリー集合しゅうごう論ろんタルスキ＝グロタンディーク集合しゅうごう論ろん（英語えいご版ばん）
モデル理論りろん	モデル（英語えいご版ばん）解釈かいしゃく（英語えいご版ばん）超ちょう準じゅんモデル（英語えいご版ばん）有限ゆうげんモデル理論りろん真理しんり値ち妥当だとう性せい
証明しょうめい論ろん	形式けいしき的てき証明しょうめい演繹えんえきシステム（英語えいご版ばん）形式けいしき体系たいけい定理ていり論理ろんり的てき帰結きけつ推論すいろん規則きそく統語とうご論ろん（英語えいご版ばん）シークエント計算けいさん
計算けいさん理論りろん再帰さいき理論りろん	計算けいさん可能かのう性せい計算けいさん複雑ふくざつ性せい複雑ふくざつ性せいクラス P≠NP予想よそう再帰さいき帰納的きのうてき集合しゅうごう帰納的きのうてき可算かさん集合しゅうごう決定けってい問題もんだい停止ていし性せい問題もんだいチャーチ＝チューリングのテーゼ計算けいさん可能かのう関数かんすう原始げんし再帰さいき関数かんすう μみゅー再帰さいき関数かんすうチューリングマシンラムダ計算けいさん