La recursión ocurre cuando la definición de un concepto o proceso depende de una versión más simple o previa de sí mismo. [1] La recursión 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 recursión es en matemáticas y ciencias de la computación , 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.
Un proceso que exhibe recursión es recursivo .
En matemáticas y ciencias de la computación, 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 . Un antepasado es:
La secuencia de Fibonacci es otro ejemplo clásico de recursión:
Muchos axiomas matemáticos se basan en reglas recursivas. Por ejemplo, la definición formal de los números naturales según 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 esta regla recursiva, se puede generar el conjunto de todos los números naturales.
Otros objetos matemáticos definidos recursivamente incluyen factoriales , funciones (por ejemplo, relaciones de recurrencia ), conjuntos (por ejemplo, conjunto ternario de Cantor ) y fractales .
Hay varias definiciones más irónicas de recursión; véase humor recursivo.
La recursión es el proceso por el que pasa un procedimiento cuando uno de los pasos del procedimiento implica invocar el propio procedimiento. Un procedimiento que pasa por la recursión se dice que es "recursivo". [3]
Para comprender la recursión, es necesario 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 realmente seguir las reglas y realizar los pasos.
La recursión está relacionada con, pero no es lo mismo que, una referencia dentro de la especificación de un procedimiento a la ejecución de algún otro procedimiento.
Cuando se define un procedimiento de esta manera, se crea inmediatamente la posibilidad de un bucle sin fin; la recursión sólo se puede utilizar adecuadamente en una definición si se omite el paso en cuestión en ciertos casos para que el procedimiento pueda completarse.
Incluso si se define correctamente, un procedimiento recursivo no es fácil de ejecutar para los humanos, ya que requiere distinguir la nueva invocación del procedimiento de la antigua, parcialmente ejecutada; esto requiere cierta administración en cuanto a cuánto han progresado las distintas 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 en el número de oraciones gramaticales en un idioma, y la falta de un límite superior en la longitud de las oraciones gramaticales (más allá de las restricciones prácticas como el tiempo disponible para pronunciar una), se pueden explicar como consecuencia de la recursión en el 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 las brujas son peligrosas aparece en la oración más larga. Por lo tanto, una oración se puede definir de forma recursiva (de manera 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 recursión.
Esto proporciona una manera de entender 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 que... Hay muchas estructuras aparte de las oraciones que se pueden definir recursivamente y, por lo tanto, muchas maneras 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 han demostrado ser susceptibles a este tipo de análisis.
La idea generalmente aceptada de que la recursión es una propiedad esencial del lenguaje humano ha sido cuestionada por Daniel Everett basándose en sus afirmaciones sobre la lengua pirahã . Andrew Nevins, David Pesetsky y Cilene Rodrigues se encuentran entre muchos otros que han argumentado en contra de esto. [7] En cualquier caso, se puede argumentar que la autorreferencia literaria es de un tipo diferente a la recursión matemática o lógica. [8]
La recursión 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 significados de oraciones para crear nuevas oraciones, y lo mismo para significados de frases nominales, significados de frases verbales y otros. También puede aplicarse a verbos intransitivos, verbos transitivos o verbos ditransitivos. Con el fin de proporcionar una única denotación para ella que sea adecuadamente flexible, y se define típicamente de modo que pueda tomar cualquiera de estos diferentes tipos de significados como argumentos. Esto se puede hacer definiéndola para un caso simple en el que combina oraciones, y luego definiendo los otros casos recursivamente en términos del simple. [9]
Una gramática recursiva es una gramática formal que contiene reglas de producción recursiva . [10]
La recursión se utiliza a veces con humor en los libros de texto de informática, programación, filosofía o matemáticas, generalmente dando una definición circular o autorreferencial , 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 dichos libros incluyan una entrada de broma en su glosario del tipo:
Una variación se encuentra 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 del índice se referencia a sí misma recursivamente ("recursion 86, 139, 141, 182, 202, 269"). Se pueden encontrar versiones tempranas de este chiste 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 el 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 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. [12] [13]
Otro chiste es que "Para entender la recursión, debes entender la recursión". [11] En la versión en inglés del motor de búsqueda web Google, cuando se realiza una búsqueda de "recursión", el sitio sugiere "¿Quiso decir: recursión ?". [14] Una forma alternativa es la siguiente, de Andrew Plotkin : "Si ya sabes qué es la recursión, simplemente recuerda la respuesta. De lo contrario, encuentra a alguien que esté más cerca de Douglas Hofstadter que tú; luego pregúntale qué es la recursión".
Las siglas recursivas son otros ejemplos de humor recursivo. PHP , por ejemplo, significa "PHP Hypertext Preprocessor" (Preprocesador de hipertexto PHP), WINE significa "WINE Is Not an Emulator" (WINE no es un emulador), GNU significa "GNU's not Unix" (GNU no es Unix) y SPARQL denota "SPARQL Protocol and RDF Query Language" (Protocolo SPARQL y lenguaje de consulta RDF).
El ejemplo canónico de un conjunto definido recursivamente está 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 haciendo referencia a una función sucesora recursiva y a la adición 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 recursión que se puede utilizar para crear imágenes de tipo fractal. Una regla de subdivisión comienza con una colección de polígonos etiquetados con un número finito de etiquetas y, a continuación, cada polígono se subdivide en polígonos etiquetados más pequeños de una manera que depende únicamente 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 .
Una función puede definirse recursivamente en términos de sí misma. Un ejemplo conocido es la secuencia numérica de Fibonacci : F ( n ) = F ( n − 1) + F ( n − 2). Para que una definición de este tipo sea útil, debe ser reducible a valores definidos de forma no recursiva: en este caso, F (0) = 0 y F (1) = 1.
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 y ciencia informática.
La programación dinámica es un enfoque de optimización que reformula un problema de optimización de varios periodos o de varios pasos en forma recursiva. El resultado clave de 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 en un paso anterior) en términos de su valor en un momento posterior (o en un 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 de la teoría de conjuntos mediante recursión, y presentó un esbozo de un argumento en el ensayo de 1888 "¿Qué son y cómo se deben los números?" [15].
Tome dos funciones y tales 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 todo .
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 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 recursión es la definición de la función factorial , dada aquí en código Python :
def factorial ( n ): si n > 0 : devuelve n * factorial ( n - 1 ) de lo contrario : devuelve 1La función se llama a sí misma recursivamente 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 manera análoga a la definición matemática de factorial.
La recursión en la programación informática se ejemplifica cuando se define una función en términos de versiones más simples, a menudo más pequeñas, de sí misma. La solución al problema se idea entonces combinando las soluciones obtenidas a partir de las versiones más simples del problema. Un ejemplo de aplicación de la recursión es en los analizadores sintácticos para lenguajes de programación. La gran ventaja de la recursión es que un programa informático 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 relaciones de recurrencia se pueden "resolver" para obtener una definición no recursiva (por ejemplo, una expresión de forma cerrada ).
El uso de la recursión 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, lo que los vuelve poco prácticos para instancias más grandes.
En plantas y animales aparecen a veces formas que parecen haber sido creadas mediante procesos recursivos, como en las 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 . [16]
Los autores utilizan el concepto de recursividad para poner de relieve 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 se relaciona 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 que pertenecen al mundo que analizamos)”. [19] A partir de esta base, ella identifica en la recursividad un desafío fundamental en la producción de conocimiento emancipador que exige el ejercicio de esfuerzos reflexivos :
Estamos 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 intentamos 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 producidas por este mundo– evidencia la necesidad vital de implementar la reflexividad en la práctica y plantea el principal desafío para hacerlo.
—Audrey Alejandro, Alejandro (2021)
En la ciencia de la gestión, a veces se hace referencia a la recursión 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 gerencia de línea hasta la gerencia superior pasando por la gerencia media . También abarca la cuestión más amplia de la estructura de capital en la gobernanza corporativa . [21]
La muñeca Matrioska es un ejemplo artístico físico del concepto recursivo. [22]
La recursión 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 el efecto Droste , un ejemplo de la técnica de Mise en abyme .
La Galería de Estampas de MC Escher (1956) es una estampa que representa una ciudad distorsionada que contiene una galería que contiene recursivamente la imagen, y así hasta el infinito . [25]
En la película Origen se ha adoptado la costumbre de añadir el sufijo -cepción a un sustantivo para indicar en tono de broma la recursión de algo. [26]
Más ejemplos de recursión: muñecas rusas Matryoshka. Cada muñeca está hecha de madera maciza o es hueca y contiene otra muñeca Matryoshka en su interior.
