recursion

ウィキペディア

再帰

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/23 05:02 UTC 版)

「リカーシブ」と「リカーシブル」はこの項目へ転送されています。米澤穂信の小説については「リカーシブル (小説)」をご覧ください。

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

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

定義

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

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

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

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

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

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

• 基底1として${\displaystyle 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"を表す。

  数学

  

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

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

  再帰的定義

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

  例: 自然数

  →「閉包」も参照

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

  0 は${\displaystyle \mathbb {N} }$

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

  

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

  →「ドロステ効果」も参照

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

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

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

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

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

  類似する概念

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

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

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

  • 帰納 - 証明手続きの方向性として「基底段階の小さなものから段々と大きい（普遍的な）もの」へと進んでいく。特に数学的帰納法の帰納段階では、任意の自然数${\displaystyle k}$

ウィキメディア・コモンズには、再帰に関連するカテゴリがあります。