La recursividad ocurre cuando la definición de un concepto o proceso depende de una versión más simple o anterior del mismo. [1] 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 pueda ocurrir ningún bucle infinito o cadena infinita de referencias.
Un proceso que exhibe recursividad es recursivo .
En matemáticas e informática, una clase de objetos o métodos exhibe un comportamiento recursivo cuando puede definirse mediante dos propiedades:
Por ejemplo, la siguiente es una definición recursiva del antepasado de una persona . El antepasado de uno es:
La secuencia de Fibonacci es otro ejemplo clásico de recursividad:
Muchos axiomas matemáticos se basan en reglas recursivas. Por ejemplo, la definición formal de los números naturales mediante 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". [2] Mediante este caso base y regla recursiva, se puede generar el conjunto de todos los números naturales.
Otros objetos matemáticos definidos recursivamente incluyen factoriales , funciones (p. ej., relaciones de recurrencia ), conjuntos (p. ej., conjunto ternario de Cantor ) y fractales .
Hay varias definiciones más irónicas de recursividad; ver humor recursivo.
La recursividad es el proceso por el que pasa un procedimiento cuando uno de sus pasos implica invocar el procedimiento mismo. Un procedimiento que pasa por recursión se dice que es "recursivo". [3]
Para comprender la recursividad, hay que 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 las reglas y realizar los pasos.
La recursividad está relacionada con una referencia dentro de la especificación de un procedimiento a la ejecución de algún otro procedimiento, pero no es lo mismo.
Cuando se define así un procedimiento, se crea inmediatamente la posibilidad de un bucle sin fin; La recursividad solo se puede utilizar correctamente en una definición si el paso en cuestión se omite en ciertos casos para que se pueda completar el procedimiento.
Incluso si se define adecuadamente, un procedimiento recursivo no es fácil de realizar para los humanos, ya que requiere distinguir la invocación nueva del procedimiento, parcialmente ejecutada; Esto requiere cierta administración en cuanto a hasta qué punto han progresado varias instancias simultáneas de los procedimientos. Por esta razón, las definiciones recursivas son muy raras en situaciones cotidianas.
El lingüista Noam Chomsky , entre muchos otros, ha argumentado que la falta de un límite superior para el número de oraciones gramaticales en una lengua y la falta de un límite superior para la longitud de las oraciones gramaticales (más allá de limitaciones prácticas como el tiempo disponible para pronunciar una ), puede explicarse como consecuencia de la recursividad en el lenguaje natural. [4] [5]
Esto puede entenderse 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 las brujas son peligrosas aparece en la oración más grande. Por lo tanto, una oración se puede definir recursivamente (de manera muy aproximada) como algo con una estructura que incluye un sintagma 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 comprender la creatividad del lenguaje (el número ilimitado de oraciones gramaticales) porque predice inmediatamente que las oraciones pueden tener una longitud arbitraria: Dorothy piensa que Toto sospecha que el Hombre de Hojalata dijo eso ... 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, las lenguas en general han demostrado ser susceptibles a este tipo de análisis.
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 muchos que se han opuesto a esto. [7] En cualquier caso, se puede argumentar que la autorreferencia literaria es diferente de la recursión 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, puede interpretarse como una función que puede aplicarse a los significados de oraciones para crear nuevas oraciones, y también a los significados de frases sustantivas, verbales y otras. También se puede aplicar a verbos intransitivos, verbos transitivos o verbos ditransitivos. Para proporcionarle una denotación única que sea adecuadamente flexible y que generalmente se defina de manera 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 recursivamente en términos del caso simple. [9]
Una gramática recursiva es una gramática formal que contiene reglas de producción recursivas . [10]
La recursividad a veces se usa con humor en los libros de texto de informática, programación, filosofía o matemáticas, generalmente dando una definición circular o autorreferencia , en la que el supuesto paso recursivo no se acerca a un caso base, sino que conduce a una regresión infinita. . No es inusual que estos libros incluyan una entrada de chiste en su glosario como:
Se encuentra una variación en la página 269 del índice de algunas ediciones del libro de Brian Kernighan y Dennis Ritchie The C Programming Language ; la entrada del índice hace referencia recursiva a sí misma ("recursión 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 fecha de copyright de 1976) y en Software Tools de Kernighan y Plauger (publicado por Addison-Wesley Professional en 11 de enero de 1976). El chiste 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 folklore 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. [12] [13]
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 web Google, cuando se realiza una búsqueda de "recursividad", el sitio sugiere "¿Quiso decir: recursividad ?". [14] Una forma alternativa es la siguiente, de Andrew Plotkin : "Si ya sabe qué es la recursividad, simplemente 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 indica "Protocolo SPARQL y lenguaje de consulta RDF".
El ejemplo canónico de un conjunto definido recursivamente viene dado por los números naturales :
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 refiriéndose a una función sucesora recursiva y la suma y multiplicación como funciones recursivas.
Otro ejemplo interesante es el conjunto de todas las proposiciones "demostrables" en un sistema axiomático que se definen en términos de un procedimiento de prueba que se define inductivamente (o recursivamente) de la siguiente manera:
Las reglas de subdivisión finita son una forma geométrica de recursividad que se puede utilizar para crear imágenes similares a 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 repetir. 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 .
Una función puede definirse recursivamente 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 tal 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 necesaria ]
La aplicación de la técnica estándar de prueba por casos a conjuntos o funciones definidos recursivamente, como en las secciones anteriores, produce la inducción estructural , una poderosa generalización de la inducción matemática ampliamente utilizada para derivar pruebas en lógica matemática e informática.
La programación dinámica es un enfoque de optimización que reformula un problema de optimización de varios períodos o de varios pasos en 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).
En 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 existe una función única (donde denota el conjunto de números naturales incluido el cero) tal que
para cualquier número natural n .
Dedekind fue el primero en plantear el problema de la definición única de funciones teóricas de conjuntos por recursión, y esbozó un argumento en el ensayo de 1888 "Was sind und was sollen die Zahlen?" [15]
Tome dos funciones y tal que:
donde a 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 :
Por inducción, F ( n ) = G ( n ) para todos .
Un método común de simplificación es dividir un problema en subproblemas del mismo tipo. Como técnica de programación informática , esto se llama divide y vencerás y es clave para el diseño de muchos algoritmos importantes. Divide y vencerás sirve como un enfoque de arriba hacia abajo para la resolución de problemas, donde los problemas se resuelven resolviendo instancias cada vez más pequeñas. Un enfoque contrario es la programación dinámica . Este enfoque sirve como un enfoque ascendente, donde los problemas se resuelven resolviendo instancias cada vez más grandes, hasta alcanzar el tamaño deseado.
Un ejemplo clásico de recursividad es la definición de la función factorial , que se proporciona aquí en código Python :
def factorial ( n ): si n > 0 : devuelve n * factorial ( n - 1 ) en caso contrario : devuelve 1La 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 informática 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 se idea la solución al problema combinando las soluciones obtenidas de las versiones más simples del problema. Un ejemplo de aplicación de recursividad son los analizadores de lenguajes de programación. La gran ventaja de la recursividad es que un programa de computadora finito puede definir, analizar o producir un conjunto infinito de posibles oraciones, diseños u otros datos.
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 simplicidad 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.
A veces aparecen formas que parecen haber sido creadas mediante procesos recursivos en plantas y animales, como en estructuras ramificadas en las que una parte grande se ramifica en dos o más partes más pequeñas similares. Un ejemplo es el brócoli romanesco . [dieciséis]
Los autores utilizan el concepto de recursividad para poner en primer plano la situación en la que se encuentran específicamente los científicos sociales cuando producen conocimiento sobre el mundo del que siempre forman parte. [17] [18] Según Audrey Alejandro, “como científicos sociales, la recursividad de nuestra condición tiene que ver con el hecho de que somos a la vez sujetos (ya que los discursos son el medio a través del cual analizamos) y objetos de los discursos académicos que producimos ( ya que somos agentes sociales pertenecientes al mundo que analizamos).” [19] A partir de esta base, identifica en la recursividad un desafío fundamental en la producción de conocimiento emancipador que exige el ejercicio de esfuerzos reflexivos :
somos socializados en discursos y disposiciones producidos por el orden sociopolítico que pretendemos desafiar, un orden sociopolítico que, por lo tanto, podemos reproducir inconscientemente mientras pretendemos hacer lo contrario. La recursividad de nuestra situación como académicos –y, más precisamente, el hecho de que las herramientas disposicionales que utilizamos para producir conocimiento sobre el mundo son a su vez producidas por este mundo– evidencia la necesidad vital de implementar la reflexividad en la práctica y plantea el principal desafío en la investigación. haciéndolo.
—Audrey Alejandro, Alejandro (2021)
En la ciencia de la gestión , a veces se hace referencia a la recursividad como el proceso de iteración a través de niveles de abstracción en grandes entidades comerciales. [20] Un ejemplo común es la naturaleza recursiva de las jerarquías de gestión , que van desde la dirección de línea hasta la alta dirección pasando por la dirección intermedia . También abarca la cuestión más amplia de la estructura de capital en el gobierno corporativo . [21]
La muñeca Matryoshka es un ejemplo artístico físico del concepto recursivo. [22]
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 una ofrenda. [23] [24] Esta práctica se conoce más generalmente como efecto Droste , un ejemplo de la técnica Mise en abyme .
MC Escher 's Print Gallery (1956) es un grabado que representa una ciudad distorsionada que contiene una galería que contiene recursivamente la imagen, y así hasta el infinito . [25]
La película Inception ha coloquializado la adición del sufijo -ception a un sustantivo para indicar en broma la recursión de algo. [26]
Más ejemplos de recursividad: muñecas rusas Matryoshka.
Cada muñeca está hecha de madera maciza o es hueca y contiene otra muñeca Matryoshka en su interior.
