Definición recursiva

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

En matemáticas e informática , una definición recursiva , o definición inductiva , se utiliza para definir los elementos de un conjunto en términos de otros elementos del mismo conjunto ( Aczel 1977:740 y ss.). 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$ $!$ 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$ , ya que la recursión finalmente alcanza el caso base de 0. La definición también puede interpretarse 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 afirma que dicha definición define una función que es única. La demostración utiliza 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 ⁠ $\mathbb {N}$ de números naturales es:

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

Existen muchos conjuntos que satisfacen (1) y (2); por ejemplo, el conjunto ${0, 1, 1.649, 2, 2.649, 3, 3.649, \dots}$ cumple la definición. Sin embargo, la condición (3) especifica el conjunto de los números naturales eliminando los conjuntos con elementos superfluos.

Las propiedades de funciones y conjuntos definidos recursivamente a menudo pueden demostrarse mediante un principio de inducción derivado de la definición recursiva. Por ejemplo, la definición de los números naturales que se presenta 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 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 (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 esos casos base que terminan la recursión), una regla también conocida como "recurre 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 en función de otros valores de la función. Tal situación 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 demostración no es trivial. ^{[ 3 ]} Donde 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$ , $f(0),f(1),\dots ,f(n-1)$ (es decir, cláusula inductiva).

En términos más generales, se pueden crear 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 en el caso general. Un resumen de la demostración general y los criterios se pueden encontrar en la obra " Topology" de James Munkres . Sin embargo, a continuación se presentará un caso específico (el dominio se restringe a los enteros positivos en lugar de a cualquier conjunto bien ordenado) de la definición recursiva general. ^[⁴^]

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 única función $h:\mathbb {Z} _{+}\to A$ de tal manera que

{\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 en función del 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 conjunto único de enteros positivos que satisfacen

2 es un número primo,
Cualquier otro número entero positivo es un número primo si y solo 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$ mediante esta definición requiere conocer la primalidad de todos los enteros entre 2 y $X$ , lo cual está bien definido por esta definición. Este último punto puede probarse por inducción sobre $X$ , para lo cual es esencial que la segunda cláusula diga "si y solo si"; si solo dijera "si", la primalidad de, por ejemplo, el número 4 no serí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 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 la base y de las cláusulas inductivas (cláusula extremal).

Fórmula bien formulada

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

$p$ es una fórmula bien formada si $p$ es una variable proposicional.
$\neg p$ es una fórmula bien formada si $p$ es una fórmula bien formada.
$(p • q)$ es una fwf si $p$ y $q$ son fwf y • es uno de los conectores lógicos ∨, ∧, → o ↔.

La definición se puede utilizar para determinar si una cadena de símbolos determinada es una fórmula bien formada:

$(p \land q)$ es una fwf, porque las variables proposicionales $p$ y $q$ son fwf y $\land$ es un conector lógico.

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

$(\neg p \land \neg q)$ es una fwf, porque $\neg p$ y $\neg q$ son fwf y $\land$ es un conector 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 puede escribirse como el programa lógico:

incluso ( 0 ). incluso ( s ( s ( X ))) :- incluso ( 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 el razonamiento hacia atrás 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 solo para comprobar si una consulta es verdadera, sino también para generar respuestas 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 extienden significativamente las definiciones recursivas al incluir el uso de condiciones negativas, implementadas mediante la negación como fallo , como en la definición:

incluso ( 0 ). incluso ( s ( X )) :- no ( incluso ( 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 . Archivado del original el 2 de agosto de 2019. Consultado el 24 de octubre de 2019 .
↑ Para una demostración 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: 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). «Introducción a las definiciones inductivas». En Barwise, J. (ed.). Manual de lógica matemática . Estudios en lógica y fundamentos de las matemáticas. Vol. 90. North-Holland . pp. 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-2OCLC 636352297

[1] 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 .

[2] "Todo sobre la recursión" . www.cis.upenn.edu . Archivado del original el 2 de agosto de 2019. Consultado el 24 de octubre de 2019 .

[3] Para una demostración del Teorema de Recursión, véase Sobre la Inducción Matemática (1960) de Leon Henkin .

[Munkres-4] 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.

[5] Denecker, M., Ternovska, E.: Una lógica de definiciones inductivas no monótonas. ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)

[6] Warren, DS y Denecker, M., 2023. Una mejor semántica lógica para Prolog. En Prolog: Los próximos 50 años (págs. 82-92). Cham: Springer Nature Suiza.

[ 1 ]

[ 2 ]

[ 3 ]

[

[ 5 ]

[ 6 ]