原始再帰関数

原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。