El hecho de que tales definiciones se puedan simplificar muestra que son recursivas primitivas.
A diferencia de la recursión global, en la recursión primitiva el cálculo de una función requiere únicamente el valor anterior.
se define recursivamente por las reglas Esta recursión es primitiva porque calcula el siguiente valor (n +1)!
Por otro lado, la función Fib(n), que devuelve el n -ésimo número de Fibonacci, se define con las ecuaciones de recursión Para calcular Fib(n+2), se requieren los dos últimos valores.
En particular, g(n+1) requiere todos sus valores anteriores.
es el número de Gödel que codifica la secuencia indicada.
Dada la función por recursión global f: Basta con definir una función auxiliar para expresarla en un esquema de recursión primitiva De este modo
codifica los primeros n valores de f. La función
, la función original f se puede definir por