Funciones Recursivas
Hay varios tipos de funciones recursivas. Para explicarlas debemos introducir primero alguna terminología: una función constante es una función que tiene el mismo valor para todos sus argumentos; una función sucesora tiene como valor para cualquier argumento dado el sucesor de ese argumento; una función de identidad es una función de n argumentos cuyo valor es siempre el argumento ith. Todas estas funciones se conocen como funciones fundamentales.
Una función de n argumentos se define por composición cuando, dado cualquier conjunto de funciones previamente introducidas de n argumentos, el valor de la nueva función es igual al valor de una función previamente introducida cuyos argumentos en cualquier caso particular son los valores de cada uno de los miembros del conjunto de funciones cuando sus argumentos son los argumentos de la nueva función introducida en ese caso particular.