Definición recursiva
Una definición recursiva (o definición inductiva) en lógica matemática y ciencias de la computación se utiliza para definir los elementos de un conjunto en términos de otros elementos del conjunto (Aczel 1978:740ff).
Esta definición es válida para todos los n, porque la recursividad finalmente alcanza el caso base de 0.
El teorema de la recursividad establece que tal definición define efectivamente una función.
Por ejemplo, una definición del conjunto de números naturales N es: Hay muchos conjuntos que satisfacen (1) y (2) - por ejemplo, el conjunto {1, 1.649, 2, 2.649, 3, 3.649, ...} satisface la definición.
Las propiedades de las funciones y conjuntos definidos recursivamente se pueden probar a menudo mediante un principio de inducción que sigue la definición recursiva.
Por ejemplo, la definición de los números naturales presentados aquí implica directamente el principio de inducción matemática para los números naturales: si una propiedad tiene el número natural 0, y la propiedad tiene n+1 cuando tiene n, entonces la propiedad tiene todos los números naturales (Aczel 1978:742).
La mayoría de las definiciones recursivas tienen dos fundamentos: un caso base (base) y una cláusula inductiva.
La diferencia entre una definición circular y una definición recursiva es que una definición recursiva siempre debe tener casos base, casos que satisfacen la definición sin ser definidos en términos de la definición misma, y todos los demás casos que componen la definición deben ser "menores" (más cercanos a los casos base que terminan la recursión) en algún sentido.
En contraste, una definición circular puede no tener un caso base, y definir el valor de una función en términos de ese valor en sí mismo, más que en otros valores de la función.
Tal situación llevaría a una regresión infinita.
El hecho de que las definiciones recursivas sean válidas -lo que significa que una definición recursiva identifica una función única- es un teorema de la teoría de conjuntos, cuya prueba no es trivial.
Cuando el dominio de la función son los números naturales, las condiciones suficientes para que la definición sea válida son que el valor de
sea dado (caso base) y que, para n>0, se dé un algoritmo para determinar
De forma más genérica, las definiciones recursivas de funciones pueden hacerse siempre que el dominio sea un conjunto bien ordenado, utilizando el principio de la recursión transfinita.
Los criterios formales de lo que constituye una definición recursiva válida son más complejos para el caso general.
Sin embargo, un caso específico (el dominio está restringido a los números enteros positivos en lugar de a cualquier conjunto bien ordenado) de la definición recursiva general se dará a continuación.
sea un conjunto y dejemos que
asignando una sección no vacía de los enteros positivos a
La suma se define recursivamente basándose en el recuento
Los coeficientes binomiales se definen recursivamente
El conjunto de números primos puede definirse como el único conjunto de números enteros positivos que satisfacen La primalidad del número entero 1 es el caso base; comprobando la primalidad de cualquier número entero más grande X por esta definición requiere conocer la primalidad de cada número entero entre 1 y X, que está bien definido por dicha definición.
Este último punto puede comprobarse por inducción en X, para lo cual es esencial que la segunda cláusula diga "si y sólo si"; si hubiera dicho sólo "si" la primacía de, por ejemplo, 4 no estaría clara, y la aplicación posterior de la segunda cláusula sería imposible.
Los números pares pueden definirse como compuestos por Las definiciones recursivas se encuentran principalmente en la lógica o la programación informática.
Por ejemplo, una fórmula bien formada (wff) se puede definir como: El valor de una definición tan recursiva es que puede utilizarse para determinar si una cadena particular de símbolos está "bien formada".
