数学において、再帰（recursion）とは定義の中に自分自身が登場しているような状態を指す。
例えば、次のように定義される自然数上の関数\(f:\mathbb{N}\to\mathbb{N}\)を考える。
- \(f(n)\)の値は、\(f(0)\)からこれまでの関数\(f\)の値をすべて足し合わせた数（\(=f(0)+f(1)+\cdots+f(n-1)\)）より大きい最小の数である。
この関数（の定義）は、
- 定義文中に自分自身である\(f\)が登場している。
- \(f(0)\)から順番に値を計算することで、\(f(n)\)の値を得ることができる。
という特徴を持っている。このような性質を持っているとき、この定義は「再帰的な定義」と言われる。
具体的な操作としては、自然数上での原始再帰、あるいはより一般の項に対する再帰的な定義として行われる。そうでない場合は、関数の値が定まることを自分で示さなければならない。例えばマッカーシーの91関数や竹内のたらい回し関数は、原始再帰などの手法には依っていないため、値が定まって計算できることはそれほど自明ではない。
例[]
\(\Sigma=\{b,\sigma_1,\sigma_2,\cdots\}\)を記号の集合とする。各記号には\(\mathrm{ar}:\Sigma\to\mathbb{N}\)によって自然数が割り当てられているものとする。ここで、\(\mathrm{ar}(b)=0\)であると仮定する。
記号と括弧()を組み合わせた列の集合\(T\)を、以下によって再帰的に定義する。
- 基本のケース：\(b\in T\)。
- 再帰ステップ：ある記号\(\sigma\in\Sigma\)と項\(t_1,t_2,\cdots,t_{\mathrm{ar}(\sigma)}\in T\)に対して、\(\sigma(t_1,t_2,\cdots,t_{\mathrm{ar}(\sigma)})\in T\)。
「再帰的に定義する」とは、以上の条件によって生成されるもののみを考えるということである。つまり、項\(\sigma(t_1,\cdots,t_k)\)に対して、ここに登場する各\(t_i\)を辿ると、必ず有限回のステップのうちに基本のケースに帰着できることを要請している。
このような定義によって得られた\(T\)の元を項という。記号の数も有限であるならば、BNF記法によって以下のように書かれることもある。
- \(t::=\ b\ |\ \sigma_1(t_1,\cdots,t_{\mathrm{ar}(\sigma_1)})\ |\dots\)
項上の関数を定義するとき、\(T\)を定義したときと同様の方法で定義を定めることができる。すなわち、関数\(\varphi:T\to X\)を、以下のように再帰的に定義できる。
- 基本のケース：\(\varphi(b)\in X\)をひとつ定める。
- 再帰ステップ：\(\sigma\in\Sigma\)と\(t_1,\cdots,t_{\mathrm{ar}(\sigma)}\in T\)に対して、\(\varphi(t_1),\cdots,\varphi(t_{\mathrm{ar}(\sigma)})\)が定義できたものとして、これらから\(\varphi(\sigma(t_1,\cdots,t_{\mathrm{ar}(\sigma)}))\)を定める。
どんな項でも有限回のステップのうちに基本のケースに帰着できることから、以上を定めれば\(\varphi(t)\)は定義できることがわかる。