「リカーシブ」と「リカーシブル」はこの項目へ転送されています。米澤穂信の小説については「リカーシブル (小説)」をご覧ください。
再帰（さいき、英: 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]。
