Kleene introduce el concepto de funciones recursivas (más precisamente “funciones general-recursivas” o “recursivas generales”) como aquellas funciones sobre los números naturales que están definidas mediante un conjunto finito de operaciones básicas (como la sucesión/número siguiente, la proyección, composición, recursión primitiva, y el operador µ, que hace búsqueda) que permiten expresar una función en términos de otras funciones ya definidas, o de la misma función con argumentos más pequeños.