La recursividad (adjetivo: recursivo ) ocurre cuando una cosa se define en términos de sí misma o de su tipo. La recursividad se utiliza en una variedad de disciplinas que van desde la lingüística hasta la lógica . La aplicación más común de la recursividad es en matemáticas e informática , donde una función que se define se aplica dentro de su propia definición. Si bien esto aparentemente define un número infinito de instancias (valores de función), a menudo se hace de tal manera que no puede ocurrir un bucle infinito o una cadena infinita de referencias.
Definiciones formales
En matemáticas y ciencias de la computación, una clase de objetos o métodos exhibe un comportamiento recursivo cuando puede ser definido por dos propiedades:
- Un caso (o casos) base simple : un escenario final que no utiliza la recursividad para producir una respuesta
- Un paso recursivo : un conjunto de reglas que reduce todos los casos sucesivos hacia el caso base.
Por ejemplo, la siguiente es una definición recursiva del antepasado de una persona . El antepasado de uno es:
- Uno de los padres ( caso base ), o
- El antepasado de uno de los padres ( paso recursivo ).
La secuencia de Fibonacci es otro ejemplo clásico de recursividad:
- Fib (0) = 0 como caso base 1,
- Fib (1) = 1 como caso base 2,
- Para todos los números enteros n > 1 , Fib ( n ) = Fib ( n - 1) + Fib ( n - 2) .
Muchos axiomas matemáticos se basan en reglas recursivas. Por ejemplo, la definición formal de los números naturales por los axiomas de Peano se puede describir como: "El cero es un número natural, y cada número natural tiene un sucesor, que también es un número natural". [1] Según este caso base y la regla recursiva, se puede generar el conjunto de todos los números naturales.
Otros objetos matemáticos definidos de forma recursiva incluyen factoriales , funciones (por ejemplo, relaciones de recurrencia ), conjuntos (por ejemplo, conjunto ternario de Cantor ) y fractales . [2]
Hay varias definiciones más irónicas de la recursividad; ver humor recursivo .
Definición informal
La recursividad es el proceso por el que pasa un procedimiento cuando uno de los pasos del procedimiento implica invocar el procedimiento en sí. Se dice que un procedimiento que pasa por la recursividad es "recursivo". [3]
Para comprender la recursividad, se debe reconocer la distinción entre un procedimiento y la ejecución de un procedimiento. Un procedimiento es un conjunto de pasos basados en un conjunto de reglas, mientras que la ejecución de un procedimiento implica seguir realmente las reglas y realizar los pasos.
La recursividad está relacionada con, pero no es lo mismo, una referencia dentro de la especificación de un procedimiento a la ejecución de algún otro procedimiento.
Cuando un procedimiento se define como tal, esto crea inmediatamente la posibilidad de un bucle sin fin; la recursividad solo se puede usar correctamente en una definición si el paso en cuestión se omite en ciertos casos para que el procedimiento pueda completarse.
Pero incluso si está correctamente definido, un procedimiento recursivo no es fácil de realizar para los humanos, ya que requiere distinguir el nuevo de lo antiguo, la invocación del procedimiento parcialmente ejecutada; esto requiere cierta administración en cuanto a cuánto han progresado varias instancias simultáneas de los procedimientos. Por esta razón, las definiciones recursivas son muy raras en situaciones cotidianas.
En idioma
El lingüista Noam Chomsky , entre muchos otros, ha argumentado que la falta de un límite superior en el número de oraciones gramaticales en un idioma, y la falta de un límite superior en la longitud de la oración gramatical (más allá de las limitaciones prácticas como el tiempo disponible para pronunciar una ), se puede explicar como consecuencia de la recursividad en lenguaje natural. [4] [5]
Esto se puede entender en términos de una definición recursiva de una categoría sintáctica, como una oración. Una oración puede tener una estructura en la que lo que sigue al verbo es otra oración: Dorothy piensa que las brujas son peligrosas , en la que la oración que las brujas son peligrosas ocurre en la más grande. Por lo tanto, una oración se puede definir de forma recursiva (muy aproximada) como algo con una estructura que incluye una frase nominal, un verbo y, opcionalmente, otra oración. En realidad, este es solo un caso especial de la definición matemática de recursividad.
Esto proporciona una manera de entender la creatividad del lenguaje el número ilimitado de oraciones gramaticales-porque inmediatamente predice que las oraciones pueden ser de longitud arbitraria: Dorothy Toto piensa que sospecha que Tin Man dice que ... . Hay muchas estructuras además de las oraciones que se pueden definir de forma recursiva y, por lo tanto, muchas formas en las que una oración puede incrustar instancias de una categoría dentro de otra. [6] A lo largo de los años, los idiomas en general se han mostrado receptivos a este tipo de análisis.
Sin embargo, recientemente, la idea generalmente aceptada de que la recursividad es una propiedad esencial del lenguaje humano ha sido cuestionada por Daniel Everett sobre la base de sus afirmaciones sobre el idioma pirahã . Andrew Nevins, David Pesetsky y Cilene Rodrigues se encuentran entre los muchos que han argumentado en contra de esto. [7] En cualquier caso, se puede argumentar que la autorreferencia literaria es diferente de la recursividad matemática o lógica. [8]
La recursividad juega un papel crucial no solo en la sintaxis, sino también en la semántica del lenguaje natural . La palabra y , por ejemplo, se puede interpretar como una función que se puede aplicar a los significados de las oraciones para crear nuevas oraciones, y también para los significados de las frases nominales, de las frases verbales y otros. También se puede aplicar a verbos intransitivos, verbos transitivos o verbos ditransitivos. Con el fin de proporcionarle una sola denotación que sea adecuadamente flexible, y que se defina típicamente de modo que pueda tomar cualquiera de estos diferentes tipos de significados como argumentos. Esto se puede hacer definiéndolo para un caso simple en el que combina oraciones, y luego definiendo los otros casos de forma recursiva en términos del simple. [9]
Una gramática recursiva es una gramática formal que contiene reglas de producción recursivas . [10]
Humor recursivo
La recursividad a veces se usa con humor en los libros de texto de ciencias de la computación, programación, filosofía o matemáticas, generalmente dando una definición circular o autorreferencia , en la que el paso recursivo putativo no se acerca a un caso base, sino que conduce a una regresión infinita. . No es inusual que tales libros incluyan una entrada de broma en su glosario como:
- Recursividad, consulte Recursividad . [11]
Se encuentra una variación en la página 269 en el índice de algunas ediciones del libro de Brian Kernighan y Dennis Ritchie The C Programming Language ; la entrada de índice se referencia recursivamente a sí misma ("recursividad 86, 139, 141, 182, 202, 269"). Las primeras versiones de este chiste se pueden encontrar en Let's talk Lisp de Laurent Siklóssy (publicado por Prentice Hall PTR el 1 de diciembre de 1975 con una fecha de copyright de 1976) y en Software Tools de Kernighan y Plauger (publicado por Addison-Wesley Professional en enero 11, 1976). La broma también aparece en The UNIX Programming Environment de Kernighan y Pike. No apareció en la primera edición de The C Programming Language . El chiste es parte del folclore de la programación funcional y ya estaba muy extendido en la comunidad de programación funcional antes de la publicación de los libros antes mencionados.
Otro chiste es que "Para entender la recursividad, debes entender la recursividad". [11] En la versión en inglés del motor de búsqueda de Google, cuando se realiza una búsqueda de "recursividad", el sitio sugiere "Quiso decir: recursividad ". [12] Una forma alternativa es la siguiente, de Andrew Plotkin : "Si ya sabe qué es la recursividad, recuerde la respuesta. De lo contrario, busque a alguien que esté más cerca de Douglas Hofstadter que usted; luego pregúntele qué es la recursividad es."
Las siglas recursivas son otros ejemplos de humor recursivo. PHP , por ejemplo, significa "Preprocesador de hipertexto PHP", WINE significa "WINE no es un emulador". GNU significa "GNU no es Unix", y SPARQL significa "Protocolo SPARQL y lenguaje de consulta RDF".
En matemáticas
Conjuntos definidos de forma recursiva
Ejemplo: los números naturales
El ejemplo canónico de un conjunto definido de forma recursiva viene dado por los números naturales :
- 0 está en
- si n está en , entonces n + 1 está en
- El conjunto de números naturales es el conjunto más pequeño que satisface las dos propiedades anteriores.
En lógica matemática, los axiomas de Peano (o postulados de Peano o axiomas de Dedekind-Peano), son axiomas para los números naturales presentados en el siglo XIX por el matemático alemán Richard Dedekind y por el matemático italiano Giuseppe Peano . Los axiomas de Peano definen los números naturales que se refieren a una función sucesora recursiva y la suma y la multiplicación como funciones recursivas.
Ejemplo: procedimiento de prueba
Otro ejemplo interesante es el conjunto de todas las proposiciones "probables" en un sistema axiomático que se definen en términos de un procedimiento de prueba que se define inductiva (o recursivamente) de la siguiente manera:
- Si una proposición es un axioma, es una proposición demostrable.
- Si una proposición puede derivarse de proposiciones verdaderas alcanzables por medio de reglas de inferencia, es una proposición demostrable.
- El conjunto de proposiciones probables es el conjunto más pequeño de proposiciones que satisfacen estas condiciones.
Reglas de subdivisión finitas
Las reglas de subdivisión finita son una forma geométrica de recursividad, que se puede utilizar para crear imágenes fractales. Una regla de subdivisión comienza con una colección de polígonos etiquetados por un número finito de etiquetas, y luego cada polígono se subdivide en polígonos etiquetados más pequeños de una manera que depende solo de las etiquetas del polígono original. Este proceso se puede iterar. La técnica estándar de los "tercios medios" para crear el conjunto de Cantor es una regla de subdivisión, al igual que la subdivisión baricéntrica .
Recursividad funcional
Una función puede definirse de forma recursiva en términos de sí misma. Un ejemplo familiar es la secuencia numérica de Fibonacci : F ( n ) = F ( n - 1) + F ( n - 2). Para que dicha definición sea útil, debe ser reducible a valores definidos de forma no recursiva: en este caso F (0) = 0 y F (1) = 1.
Una función recursiva famosa es la función de Ackermann , que, a diferencia de la secuencia de Fibonacci, no se puede expresar sin recursividad. [ cita requerida ]
Pruebas que involucran definiciones recursivas
La aplicación de la técnica estándar de demostración por casos a conjuntos o funciones definidos de forma recursiva, como en las secciones anteriores, produce inducción estructural , una poderosa generalización de la inducción matemática ampliamente utilizada para derivar demostraciones en lógica matemática e informática.
Optimización recursiva
La programación dinámica es un enfoque de optimización que reafirma un problema de optimización de múltiples períodos o pasos de forma recursiva. El resultado clave en la programación dinámica es la ecuación de Bellman , que escribe el valor del problema de optimización en un momento anterior (o paso anterior) en términos de su valor en un momento posterior (o paso posterior).
El teorema de la recursividad
En la teoría de conjuntos , este es un teorema que garantiza que existen funciones definidas recursivamente. Dado un conjunto X , un elemento a de X y una función f : X → X , el teorema establece que hay una función única (dónde denota el conjunto de números naturales, incluido el cero), de modo que
para cualquier número natural n .
Prueba de singularidad
Toma dos funciones y tal que:
donde una es un elemento de X .
Se puede demostrar por inducción matemática que F ( n ) = G ( n ) para todos los números naturales n :
- Caso base : F (0) = a = G (0) por lo que la igualdad es válida para n = 0 .
- Paso inductivo : suponga que F ( k ) = G ( k ) para algunos . Entonces F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) .
- Por tanto, F ( k ) = G ( k ) implica F ( k + 1) = G ( k + 1) .
Por inducción, F ( n ) = G ( n ) para todos.
En ciencias de la computación
Un método común de simplificación es dividir un problema en subproblemas del mismo tipo. Como técnica de programación de computadoras , esto se llama divide y vencerás y es clave para el diseño de muchos algoritmos importantes. Dividir y conquistar sirve como un enfoque de arriba hacia abajo para la resolución de problemas, donde los problemas se resuelven resolviendo casos cada vez más pequeños. Un enfoque contrario es la programación dinámica . Este enfoque sirve como un enfoque de abajo hacia arriba, donde los problemas se resuelven resolviendo instancias cada vez más grandes, hasta que se alcanza el tamaño deseado.
Un ejemplo clásico de recursividad es la definición de la función factorial , dada aquí en código C :
unsigned int factorial ( unsigned int n ) { if ( n == 0 ) { return 1 ; } else { return n * factorial ( n - 1 ); } }
La función se llama a sí misma de forma recursiva en una versión más pequeña de la entrada (n - 1)
y multiplica el resultado de la llamada recursiva por n
, hasta llegar al caso base , de forma análoga a la definición matemática de factorial.
La recursividad en la programación de computadoras se ejemplifica cuando una función se define en términos de versiones más simples, a menudo más pequeñas, de sí misma. Luego, la solución al problema se concibe combinando las soluciones obtenidas de las versiones más simples del problema. Un ejemplo de aplicación de la recursividad es en analizadores de lenguajes de programación. La gran ventaja de la recursividad es que un conjunto infinito de oraciones, diseños u otros datos posibles pueden definirse, analizarse o producirse mediante un programa informático finito.
Las relaciones de recurrencia son ecuaciones que definen una o más secuencias de forma recursiva. Algunos tipos específicos de relación de recurrencia se pueden "resolver" para obtener una definición no recursiva (por ejemplo, una expresión de forma cerrada ).
El uso de la recursividad en un algoritmo tiene ventajas y desventajas. La principal ventaja suele ser la sencillez de las instrucciones. La principal desventaja es que el uso de memoria de los algoritmos recursivos puede crecer muy rápidamente, haciéndolos poco prácticos para instancias más grandes.
En biologia
Las formas que parecen haber sido creadas por procesos recursivos a veces aparecen en plantas y animales, como en estructuras ramificadas en las que una gran parte se ramifica en dos o más partes más pequeñas similares. Un ejemplo es el brócoli romanesco . [13]
En arte
La muñeca rusa o la muñeca Matryoshka es un ejemplo artístico físico del concepto recursivo. [14]
La recursividad se ha utilizado en pinturas desde el Tríptico Stefaneschi de Giotto , realizado en 1320. Su panel central contiene la figura arrodillada del Cardenal Stefaneschi, sosteniendo el tríptico como ofrenda. [15] [ verificación fallida ]
MC Escher 's Print Gallery (1956) es una impresión que representa una ciudad distorsionada que contiene una galería que forma recursiva contiene la imagen, y así ad infinitum . [dieciséis]
Ver también
- Corecursion
- Recursión de curso de valores
- Infinito digital
- Un sueño dentro de un sueño (poema)
- Efecto Droste
- Falso despertar
- Combinador de punto fijo
- Composiciones infinitas de funciones analíticas
- Bucle infinito
- Regresión infinita
- Infinitismo
- Espejo infinito
- Función iterada
- Inducción matemática
- Mise en abyme
- Reentrante (subrutina)
- Autorreferencia
- Spiegel im Spiegel
- Bucle extraño
- Recursión de cola
- Fórmula autorreferencial de Tupper
- Tortugas todo el camino hacia abajo
Referencias
- ^ "Axiomas de Peano | matemáticas" . Enciclopedia Británica . Consultado el 24 de octubre de 2019 .
- ^ "El glosario definitivo de jerga matemática superior - recursividad" . Bóveda de matemáticas . 2019-08-01 . Consultado el 24 de octubre de 2019 .
- ^ "Definición de RECURSIVO" . www.merriam-webster.com . Consultado el 24 de octubre de 2019 .
- ^ Pinker, Steven (1994). El instinto del lenguaje . William Morrow.
- ^ Pinker, Steven; Jackendoff, Ray (2005). "La facultad del lenguaje: ¿Qué tiene de especial?". Cognición . 95 (2): 201–236. CiteSeerX 10.1.1.116.7784 . doi : 10.1016 / j.cognition.2004.08.004 . PMID 15694646 . S2CID 1599505 .
- ^ Nordquist, Richard. "¿Qué es la recursividad en la gramática inglesa?" . ThoughtCo . Consultado el 24 de octubre de 2019 .
- ^ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). "Evidencia y argumentación: una respuesta a Everett (2009)" (PDF) . Idioma . 85 (3): 671–681. doi : 10.1353 / lan.0.0140 . S2CID 16915455 . Archivado desde el original (PDF) el 6 de enero de 2012.
- ^ Drucker, Thomas (4 de enero de 2008). Perspectivas sobre la historia de la lógica matemática . Springer Science & Business Media. pag. 110. ISBN 978-0-8176-4768-1.
- ^ Barbara Partee y Mats Rooth. 1983. En Rainer Bäuerle et al., Significado, uso e interpretación del lenguaje . Reimpreso en Paul Portner y Barbara Partee, eds. 2002. Semántica formal: las lecturas esenciales . Blackwell.
- ^ Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Actas de la 40ª Reunión Anual de la Asociación de Lingüística Computacional (ACL '02) , Stroudsburg, PA, EE.UU .: Asociación de Lingüística Computacional, págs. 119, doi : 10.3115 / 1073083.1073104.
- ^ a b Hunter, David (2011). Fundamentos de las matemáticas discretas . Jones y Bartlett. pag. 494. ISBN 9781449604424.
- ^ "recursividad - Búsqueda de Google" . www.google.com . Consultado el 24 de octubre de 2019 .
- ^ "Cuadro del día: Coliflor fractal" . Consultado el 19 de abril de 2020 .
- ^ Tang, Daisy. "Recursión" . Consultado el 24 de septiembre de 2015 .
Más ejemplos de recursividad: muñecas rusas Matryoshka. Cada muñeca está hecha de madera maciza o hueca y contiene otra muñeca Matryoshka en su interior.
- ^ "Giotto di Bondone y asistentes: tríptico Stefaneschi" . El Vaticano . Consultado el 16 de septiembre de 2015 .
- ^ Cooper, Jonathan (5 de septiembre de 2007). "Arte y Matemáticas" . Consultado el 5 de julio de 2020 .
Bibliografía
- Dijkstra, Edsger W. (1960). "Programación recursiva". Numerische Mathematik . 2 (1): 312–318. doi : 10.1007 / BF01386232 . S2CID 127891023 .
- Johnsonbaugh, Richard (2004). Matemáticas discretas . Prentice Hall. ISBN 978-0-13-117686-7.
- Hofstadter, Douglas (1999). Gödel, Escher, Bach: una eterna trenza dorada . Libros básicos. ISBN 978-0-465-02656-2.
- Shoenfield, Joseph R. (2000). Teoría de la recursividad . AK Peters Ltd. ISBN 978-1-56881-149-9.
- Causey, Robert L. (2001). Lógica, conjuntos y recursividad . Jones y Bartlett. ISBN 978-0-7637-1695-0.
- Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Teoría de la recursividad, Teoremas de Gödel, Teoría de conjuntos, Teoría de modelos . Prensa de la Universidad de Oxford. ISBN 978-0-19-850050-6.
- Barwise, Jon ; Moss, Lawrence S. (1996). Círculos viciosos . Centro Universitario de Stanford para el Estudio del Lenguaje y la Información. ISBN 978-0-19-850050-6.- ofrece un tratamiento de correcursión .
- Rosen, Kenneth H. (2002). Matemáticas discretas y sus aplicaciones . Universidad McGraw-Hill. ISBN 978-0-07-293033-7.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos . Mit Pr. ISBN 978-0-262-03293-3.
- Kernighan, B .; Ritchie, D. (1988). La programación C Lenguaje . Prentice Hall. ISBN 978-0-13-110362-7.
- Stokey, Nancy; Robert Lucas; Edward Prescott (1989). Métodos recursivos en dinámica económica . Prensa de la Universidad de Harvard. ISBN 978-0-674-75096-8.
- Hungerford (1980). Álgebra . Saltador. ISBN 978-0-387-90518-1., primer capítulo sobre teoría de conjuntos.
enlaces externos
- Recursión - tutorial de Alan Gauld
- Zip archivos hasta el final
- Nevins, Andrew y David Pesetsky y Cilene Rodrigues. Evidencia y argumentación: una respuesta a Everett (2009). Idioma 85.3: 671--681 (2009)