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).

Cuatro etapas en la construcción de un copo de nieve Koch. Como en muchos otros fractales, las etapas se obtienen mediante una definición recursiva.

La definición recursiva de una función define los valores de las funciones para algunas entradas en términos de los valores de la misma función para otras entradas. Por ejemplo, la función factorial n! está definida por las reglas

0! = 1.

(n+1)! = (n+1)·n!.

Esta definición es válida para todos los n, porque la recursividad finalmente alcanza el caso base de 0. También se puede pensar en la definición como un procedimiento que describe cómo construir la función n!, comenzando desde n = 0 y continuando con n = 1, n = 2, n = 3, etc...

El teorema de la recursividad establece que tal definición define efectivamente una función. La prueba utiliza inducción matemática.

Una definición inductiva de un conjunto describe los elementos de un conjunto en términos de otros elementos del conjunto. Por ejemplo, una definición del conjunto de números naturales N es:

1. 1 está en N
2. Si un elemento n está en N entonces n+1 está también en N.
3. N es la intersección de todos los conjuntos que satisfacen (1) y (2).

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. Sin embargo, la condición (3) especifica el conjunto de números naturales eliminando los conjuntos con elementos extraños.

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).

Forma de definiciones recursivas

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 $f(0)$sea dado (caso base) y que, para n>0, se da un algoritmo para determinar $f(n)$en términos de $n,f(0),f(1),...,f(n-1)$(cláusula inductiva).

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. Un resumen de la prueba general y de los criterios se puede encontrar en la 'Topología' de Munkres. 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.

Principio de Definición Recursiva

Dejemos que $A$ sea un conjunto y dejemos que $a_{0}$sea un elemento de $A$. Si $p$ es una función que asigna a cada función $f$asignando una sección no vacía de los enteros positivos a $A$, un elemento de $A$, entonces existe una función única $h:\mathbb {Z} _{+}\to A$de tal forma que

$h(1)=a_{0}$

$h(i)=\rho (h|{1,2,...,i-1})$para $i>1$

Ejemplos de definiciones recursivas

Funciones básicas

La suma se define recursivamente basándose en el recuento

$0+a=a$

$(1+n)+a=1+(n+a)$

La multiplicación se define recursivamente

$0a=0$

$(1+n)a=a+na$

La exponenciación se define recursivamente

$a^{0}=1$

$a^{1+n}=aa^{n}$

Los coeficientes binomiales se definen recursivamente

${\binom {a}{0}}=1$

${\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}$

Números primos

El conjunto de números primos puede definirse como el único conjunto de números enteros positivos que satisfacen

• El 1 no es un número primo.
• Cualquier otro número entero positivo es un número primo si y sólo si no es divisible por un número primo más pequeño que él mismo.

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.

Números pares no negativos

Los números pares pueden definirse como compuestos por

• 0 está en el conjunto E de pares no negativos (cláusula base).
• Para cualquier elemento x en el conjunto E, x+2 está en E (cláusula inductiva).
• No hay nada en E a menos que se obtenga a partir de las cláusulas de base e inducción (cláusula extrema).

Fórmulas bien formadas

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:

1. Un símbolo que representa una proposición - como p significa "Connor es abogado".
2. El símbolo de negación, seguido de una fbf (fórmula bien formada) - como Np que significa "No es cierto que Connor sea abogado".
3. Cualquiera de los cuatro conectores binarios (C, A, K, o E) seguido de dos fbfs. El símbolo K significa "ambos son ciertos", así que Kpq puede significar "Connor es abogado y a Mary le gusta la música".

El valor de una definición tan recursiva es que puede utilizarse para determinar si una cadena particular de símbolos está "bien formada".

• Kpq está bien formado, porque es K seguido por las fbfs atómicas p y q.
• NKpq está bien formado, porque es N seguido de Kpq, que a su vez es una fbf.
• KNpNq es K seguido de Np y Nq; y Np es una fbf, etc.

Véase también

• Recursión
• Inducción matemática

Referencias

• Datos: Q2466486