「リカーシブ」と「リカーシブル」はこの項目へ転送されています。米澤穂信の小説については「リカーシブル (小説)」をご覧ください。
再帰（さいき、英: 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]。この基底段階および再帰を用いた法則によって、全ての自然数の集合を生成できる。
他にも再帰を用いて定義されている数学的対象としては、関数の漸化式、集合のカントール集合、フラクタル分野、プログラミング言語における階乗、などがある。 言語学者ノーム・チョムスキーらは、言語において適格文
言語
これは、文章など統語範疇での再帰的定義という観点から理解可能である。文章では、動詞の補語などが別の文章という構造を持つことができる。「ドロシーは魔女が危険だと考えている」には「魔女は危険だ」の一文がより大きな文章に含まれている。それゆえ文章とは、名詞句と動詞に別の文章を含みうる構造を持つものだと、再帰的に（非常に大まかだが）定義することができる。
これは、文章が任意の長さになり得ることも意味する。例えば、英語だと関係代名詞の"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 は 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
例: 証明手続き
