Definición recursiva

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

En matemáticas e informática , se utiliza una definición recursiva , o definición inductiva , para definir los elementos de un conjunto en términos de otros elementos del conjunto ( Aczel 1977:740ff). Algunos ejemplos de objetos definibles recursivamente incluyen factoriales , números naturales , números de Fibonacci y el conjunto ternario de Cantor .

Una definición recursiva de una función define los valores de la función para algunas entradas en términos de los valores de la misma función para otras entradas (generalmente más pequeñas). Por ejemplo, la función factorial $n$ $!$ está definido por las reglas

{\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}

Esta definición es válida para cada número natural $n$ , porque la recursividad eventualmente alcanza el caso base de 0. También se puede considerar que la definición proporciona un procedimiento para calcular el valor de la función $n .$ , comenzando desde $n = 0$ y continuando con $n = 1, 2, 3$ , etc.

El teorema de la recursividad establece que tal definición define una función que es única. La prueba utiliza la inducción matemática . ^[1]

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 es: $\mathbb {N}$

1 está en $\mathbb {N}.$
Si un elemento n está en entonces $n$ $+ 1$ está en $\mathbb {N}$ $\mathbb {N}.$
$\mathbb {N}$ es el conjunto más pequeño que satisface (1) y (2).

Hay muchos conjuntos que satisfacen (1) y (2); por ejemplo, el conjunto ${1, 1.649, 2, 2.649, 3, 3.649,\dots}$ satisface la definición. Sin embargo, la condición (3) especifica el conjunto de números naturales eliminando los conjuntos con miembros extraños.

Las propiedades de funciones y conjuntos definidos recursivamente a menudo pueden demostrarse mediante un principio de inducción que sigue la definición recursiva. Por ejemplo, la definición de los números naturales presentada aquí implica directamente el principio de inducción matemática para los números naturales: si una propiedad se cumple para el número natural 0 (o 1), y la propiedad se cumple para $n + 1$ siempre que se cumple para $n$ , entonces la propiedad se cumple para todos los números naturales (Aczel 1977: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 estar definidos en términos de la definición misma, y que todas las demás instancias en las cláusulas inductivas deben ser "más pequeñas". en cierto sentido (es decir, más cerca de aquellos casos base que terminan la recursividad), una regla también conocida como "recurrir sólo con un caso más simple". ^[2]

Por el contrario, una definición circular puede no tener un caso base, e incluso puede definir el valor de una función en términos de ese valor en sí mismo, en lugar de otros valores de la función. Una situación así conduciría a una regresión infinita .

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 conocido como teorema de recursividad , cuya demostración no es trivial. ^[3] Cuando el dominio de la función son los números naturales, condiciones suficientes para que la definición sea válida son que se dé el valor de $f (0) (es decir, el caso base) y que para$ $n > 0$ , se utilice un algoritmo. dado para determinar $f (n)$ en términos de $n$ , (es decir, cláusula inductiva). $f(0),f(1),\dots,f(n-1)$

De manera más general, se pueden hacer definiciones recursivas de funciones siempre que el dominio sea un conjunto bien ordenado , utilizando el principio de recursividad transfinita . Los criterios formales sobre lo que constituye una definición recursiva válida son más complejos para el caso general. Un resumen de la prueba general y los criterios se puede encontrar en la Topología de James Munkres . Sin embargo, a continuación se dará un caso específico (el dominio está restringido a los números enteros positivos en lugar de cualquier conjunto bien ordenado) de la definición recursiva general. ^[4]

Principio de definición recursiva.

Sea $A$ un conjunto y sea $a 0$ un elemento de $A.$ Si $ρ$ es una función que asigna a cada función $f$ mapeando una sección no vacía de los enteros positivos en $A$ , un elemento de $A$ , entonces existe una función única tal que $h:\mathbb {Z} _ {+}\a A$

{\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\} }\right){\text{ para }}i>1.\end{aligned}}

Ejemplos de definiciones recursivas

Funciones elementales

La suma se define recursivamente basándose en contar como

{\begin{aligned}&0+a=a,\\&(1+n)+a=1+(n+a).\end{aligned}}

La multiplicación se define recursivamente como

{\begin{aligned}&0\cdot a=0,\\&(1+n)\cdot a=a+n\cdot a.\end{aligned}}

La exponenciación se define recursivamente como

{\begin{aligned}&a^{0}=1,\\&a^{1+n}=a\cdot a^{n}.\end{aligned}}

Los coeficientes binomiales se pueden definir de forma recursiva como

{\begin{aligned}&{\binom {a}{0}}=1,\\&{\binom {1+a}{1+n}}={\frac {(1+a) {\binom {a}{n}}}{1+n}}.\end{aligned}}

números primos

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

2 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 ningún número primo menor que él mismo.

La primalidad del número entero 2 es el caso base; comprobar la primalidad de cualquier número entero mayor $X$ según esta definición requiere conocer la primalidad de cada número entero entre 2 y $X$ , que está bien definido por esta definición. Ese último punto puede probarse por inducción sobre $X$ , para lo cual es esencial que la segunda cláusula diga "si y sólo si"; si simplemente hubiera dicho "si", la primalidad de, por ejemplo, el número 4 no estaría clara y la aplicación ulterior de la segunda cláusula sería imposible.

Números pares no negativos

Los números pares se pueden definir como compuestos por

0 está en el conjunto $E$ de pares no negativos (cláusula básica),
Para cualquier elemento $x$ en el conjunto $E$ , $x + 2$ está en $E$ (cláusula inductiva),
Nada está en $E$ a menos que se obtenga de las cláusulas base e inductiva (cláusula extrema).

Fórmula bien formada

La noción de fórmula bien formada (wff) en lógica proposicional se define recursivamente como el conjunto más pequeño que satisface las tres reglas:

$p$ es un wff si $p$ es una variable proposicional.
$\neg p$ es un wff si $p$ es un wff.
$(p • q)$ es un wff si $p$ y $q$ son wffs y • es uno de los conectivos lógicos ∨, ∧, → o ↔.

La definición se puede utilizar para determinar si una cadena de símbolos en particular es un wff:

$(p \land q)$ es un wff, porque las variables proposicionales $p$ y $q$ son wffs y $\land$ es un conectivo lógico.

$\neg (p \land q)$ es un wff, porque $(p \land q)$ es un wff.

$(\neg p \land \neg q)$ es un wff, porque $\neg p$ y $\neg q$ son wffs y $\land$ es un conectivo lógico.

Definiciones recursivas como programas lógicos.

Los programas lógicos pueden entenderse como conjuntos de definiciones recursivas . ^[5]^[6] Por ejemplo, la definición recursiva de número par se puede escribir como el programa lógico:

incluso ( 0 ). par ( s ( s ( X )))  :-  par ( X ).

Aquí :-representa si , y representa el sucesor de , es decir , como en la aritmética de Peano . s(X)XX+1

El lenguaje de programación lógica Prolog utiliza razonamiento inverso para resolver objetivos y responder consultas. Por ejemplo, dada la consulta, produce la respuesta . Dada la consulta, produce la respuesta .?- even(s(s(0)))true?- even(s(0))false

El programa se puede utilizar no sólo para comprobar si una consulta es verdadera, sino también para generar respuestas que sean verdaderas. Por ejemplo:

?-  par ( X ). X  =  0 X  =  s ( s ( 0 )) X  =  s ( s ( s ( s ( 0 )))) X  =  s ( s ( s ( s ( s ( s ( 0 ) ) )))) .. ...

Los programas lógicos amplían significativamente las definiciones recursivas al incluir el uso de condiciones negativas, implementadas por negación como falla , como en la definición:

incluso ( 0 ). incluso ( s ( X ))  :-  no ( incluso ( X )).

Ver también

Notas

^ Henkin, León (1960). "Sobre la inducción matemática". El Mensual Matemático Estadounidense . 67 (4): 323–338. doi :10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
^ "Todo sobre la recursividad". www.cis.upenn.edu . Consultado el 24 de octubre de 2019 .
^ Para una prueba del teorema de la recursión, consulte Sobre la inducción matemática (1960) de Leon Henkin.
^ Munkres, James (1975). Topología, un primer curso (1ª ed.). Nueva Jersey: Prentice-Hall. pag. 68, ejercicios 10 y 12. ISBN 0-13-925495-1.
^ Denecker, M., Ternovska, E.: Una lógica de definiciones inductivas no monótonas. Transmisión ACM. Computadora. Registro. 9(2), 14:1–14:52 (2008)
^ Warren, DS y Denecker, M., 2023. Una mejor semántica lógica para el prólogo. En Prólogo: Los próximos 50 años (págs. 82-92). Cham: Springer Nature Suiza.

Referencias

Halmos, Paul (1960). Teoría de conjuntos ingenua . van Nostrand . OCLC 802530334.
Aczel, Peter (1977). "Una introducción a las definiciones inductivas". En Barwise, J. (ed.). Manual de lógica matemática . Estudios de Lógica y Fundamentos de las Matemáticas. vol. 90. Holanda Septentrional . págs. 739–782. doi :10.1016/S0049-237X(08)71120-0. ISBN 0-444-86388-5.
Hein, James L. (2010). Estructuras discretas, lógica y computabilidad . Jones y Bartlett . ISBN 978-0-7637-7206-2. OCLC 636352297.