En la teoría de la computabilidad, la recursión primitiva define una clase de funciones que se construyen mediante composición y recursión, formando un subconjunto estricto de las funciones computables. Se definen a partir de funciones básicas como la función cero, la función sucesor (basada en los axiomas de Peano) y las proyecciones, combinadas mediante reglas de composición y recursión primitiva. Muchas operaciones aritméticas comunes, como la suma, la división, el factorial o el cálculo del enésimo primo, pueden expresarse fácilmente con este esquema. Sin embargo, no todas las funciones computables son primitivas recursivas; esta limitación se demuestra mediante una variante del argumento de diagonalización de Cantor. La prueba consiste en asignar un número único a cada definición de función primitiva recursiva, lo que permite ordenarlas y evidenciar que existen funciones computables que escapan a este esquema. Para abarcar todas las funciones computables, se añade el operador de búsqueda no acotada, dando lugar a las funciones recursivas generales, de las cuales las primitivas son solo un subconjunto estricto.