Como ejemplo de ellas se tiene la suma, la división, el factorial, el enésimo primo, etc. De hecho, no es fácil definir una función que sea recursiva pero que no se pueda definir con recursión primitiva.
Una función recursiva primitiva es n-aria si toma como argumento o variable n-uplas de números naturales.
Si bien la recursión primitiva parece poder expresar cualquier operación, en realidad solamente cubre un subconjunto estricto de las funciones computables.
En conclusión, deben existir funciones computables que no son primitivas recursivas.
Este mismo argumento se puede utilizar para cualquier conjunto de funciones totales computables, por lo que cualquier enumeración (que pueda llevarse a cabo mediante un mecanismo de cómputo) de funciones computables totales es necesariamente incompleta.