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 y ciencias de la computación , 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 de forma recursiva 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 (normalmente más pequeñas). Por ejemplo, la función factorial $n$ $!$ se define mediante 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 recursión finalmente alcanza el caso base de 0. La definición también puede considerarse como 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 recursión 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 $\mathbb {N}$ números naturales es :

1 está en ⁠ ⁠ $\mathbb {N} .$
Si un elemento n está en ⁠ ⁠ $\mathbb {N}$ entonces $n + 1$ está en ⁠ ⁠ $\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 pueden demostrarse a menudo 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 cumpla 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 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 algún sentido (es decir, más cercanas a aquellos casos base que terminan la recursión), una regla también conocida como "recurrir solo 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 de este tipo conduciría a una regresión infinita .

Que las definiciones recursivas son 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 el teorema de recursión , cuya prueba no es trivial. ^[3] 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 se dé el valor de $f (0)$ (es decir, el caso base), y que para $n > 0$ , se dé un algoritmo para determinar $f (n)$ en términos de $n$ ( es decir, cláusula inductiva). $f(0),f(1),\puntos ,f(n-1)$

En términos más generales, se pueden realizar definiciones recursivas de funciones siempre que el dominio sea un conjunto bien ordenado , utilizando el principio de recursión transfinita . Los criterios formales para determinar qué constituye una definición recursiva válida son más complejos para el caso general. Se puede encontrar un esquema de la prueba general y los criterios en 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 a 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 que$ mapea 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} _{+}\to 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 el conteo 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 recursivamente 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 único conjunto de números enteros positivos que satisfacen

2 es un número primo,
cualquier otro 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 entero 2 es el caso base; comprobar la primalidad de cualquier entero mayor $X$ según esta definición requiere conocer la primalidad de cada entero entre 2 y $X$ , que está bien definida por esta definición. Este último punto se puede demostrar por inducción sobre $X$ , para lo cual es esencial que la segunda cláusula diga "si y sólo si"; si hubiera dicho simplemente "si", la primalidad de, por ejemplo, el número 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 se pueden definir como compuestos de

0 está en el conjunto $E$ de los pares no negativos (cláusula base),
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 inductivas (cláusula extrema).

Fórmula bien formada

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

$p$ es una función funcional perfecta si $p$ es una variable proposicional.
$\neg p$ es una fbf si $p$ es una fbf.
$(p • q)$ es una función funcional forzosa si $p$ y $q$ son funciones funcionales forzosas y • es uno de los conectivos lógicos ∨, ∧, → o ↔.

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

$(p \land q)$ es una función funcional robusta, porque las variables proposicionales $p$ y $q$ son funciones funcionales robustas y $\land$ es un conectivo lógico.

$\neg (p \land q)$ es una fbf, porque $(p \land q)$ es una fbf.

$(\neg p \land \neg q)$ es una función funcional robusta, porque $\neg p$ y $\neg q$ son funciones funcionales robustas 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 un número par puede escribirse como el programa lógico:

par ( 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 sí lo sean. Por ejemplo:

?-  par ( X ). X  =  0 X  =  s ( s ( 0 )) X  =  s ( s ( s ( s ( s ( 0 )))) X = s ( 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 la negación como falla , como en la definición:

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

Véase también

Notas

^ Henkin, Leon (1960). "Sobre la inducción matemática". The American Mathematical Monthly . 67 (4): 323–338. doi :10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
^ "Todo sobre la recursión". www.cis.upenn.edu . Consultado el 24 de octubre de 2019 .
^ Para una prueba del teorema de recursión, véase Sobre la inducción matemática (1960) de Leon Henkin.
^ Munkres, James (1975). Topología, un primer curso (1.ª ed.). Nueva Jersey: Prentice-Hall. pág. 68, ejercicios 10 y 12. ISBN 0-13-925495-1.
^ Denecker, M., Ternovska, E.: Una lógica de definiciones inductivas no monótonas. ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)
^ Warren, DS y Denecker, M., 2023. Una mejor semántica lógica para Prolog. En Prolog: The Next 50 Years (pp. 82-92). Cham: Springer Nature Switzerland.

Referencias

Halmos, Paul (1960). Teoría de conjuntos ingenua . van Nostrand . OCLC 802530334.
Aczel, Peter (1977). "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 & Bartlett . ISBN. 978-0-7637-7206-2.OCLC 636352297 .