Recursividad

Una forma visual de recursión conocida como el efecto Droste. La mujer en esta imagen sostiene un objeto que contiene una imagen más pequeña de su tenencia de un objeto idéntico, que a su vez contiene una imagen más pequeña de sí misma conteniendo un objeto idéntico, y así sucesivamente. 1904 Lata de cacao Droste, diseñada por Jan Musset

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 ("recurrencia crock").

Definiciones formales

Ouroboros, un símbolo antiguo que representa a una serpiente o dragón comiendo su propia cola.

En matemáticas e informática, una clase de objetos o métodos exhibe un comportamiento recursivo cuando se puede definir mediante dos propiedades:

• Un simple Caso básico (o casos) - un escenario que no utiliza la recursión para producir una respuesta
• A 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:

• El padre de uno (Caso básico), o
• El antepasado de uno de los padres (paso recursivo).

La sucesión 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 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: "Cero es un número natural, y cada número natural tiene un sucesor, que también es un número natural." Mediante este caso base y la 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.

Definición informal

Recientemente refrescante sourdough, bubbling a través de la fermentación: la receta pide una cierta agridulce que se deja de la última vez que se hace la misma receta.

La recursividad es el proceso por el que pasa un procedimiento cuando uno de los pasos del procedimiento implica la invocación del propio procedimiento. Se dice que un procedimiento que pasa por recursividad es 'recursivo'.

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 las reglas y realizar los pasos.

La recursividad 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 un procedimiento se define como tal, inmediatamente se crea la posibilidad de un ciclo 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. La recursión se presenta en tres formas: directa, indirecta y circular. La recursión directa es cuando una función (A) se invoca a sí misma (A hace referencia a A); la recursividad indirecta ocurre cuando una función (A) invoca a (B), la función (B) invoca a la función (C), la función (C) invoca a (D), etc., hasta que una de las funciones en la cadena invoca a una anterior. La recursividad circular ocurre cuando la función (A) y la función (B) se invocan entre sí. Si un ciclo infinito ocurre en recursividad directa, indirecta o circular, se dice que es la condición de "recurrencia crock." Básicamente, hay dos formas de evitar la recursividad del crock, ya sea limitar la cantidad de veces que una función puede hacer referencia a sí misma o colocar un límite absoluto en la profundidad de las llamadas a funciones, p. si hay un límite de profundidad de 50, cada vez que un procedimiento llama a otro, se incrementa un contador; cuando sale, ese contador se reduce. Una vez que el contador alcanza el límite (en este caso, 50) no se permiten más llamadas de procedimiento; si se intenta llamar a una función 51, la operación finaliza. El uso de un límite de recurrencia solo evita la recurrencia crock; colocar un límite de llamada, además de detener la recursión crock, puede tener el efecto secundario de evitar la ejecución de procedimientos complejos legítimos que están profundamente anidados, pero no son recursivos.

Pero incluso si está correctamente definido, un procedimiento recursivo no es fácil de realizar para los humanos, ya que requiere distinguir la nueva invocación parcialmente ejecutada del procedimiento de la antigua; 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 las oraciones gramaticales (más allá de restricciones prácticas como el tiempo disponible pronunciar uno), puede explicarse como consecuencia de la recursividad en el lenguaje natural.

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 grande. Entonces, una oración se puede definir recursivamente (muy aproximadamente) como algo con una estructura que incluye una frase nominal, un verbo y, opcionalmente, otra oración. Este es realmente solo un caso especial de la definición matemática de recursividad.

Esto proporciona una forma de comprender la creatividad del lenguaje (el número ilimitado de oraciones gramaticales) porque predice de inmediato que las oraciones pueden tener una longitud arbitraria: Dorothy cree que Toto sospecha que Tin Man dijo que...< /i>. Hay muchas estructuras además de las oraciones que se pueden definir de forma recursiva y, por lo tanto, muchas formas en que una oración puede incrustar instancias de una categoría dentro de otra. 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 lenguaje Pirahã. Andrew Nevins, David Pesetsky y Cilene Rodrigues se encuentran entre los muchos que han refutado este desafío. En cualquier caso, se puede argumentar que la autorreferencia literaria es de un tipo diferente de la recursividad matemática o lógica.

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 oraciones para crear nuevas oraciones, y de la misma manera para significados de frases nominales, significados de frases verbales y otros. También puede aplicarse a verbos intransitivos, verbos transitivos o verbos ditransitivos. Para proporcionar una denotación única que sea adecuadamente flexible, y se define normalmente 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 recursivamente en términos del simple.

Una gramática recursiva es una gramática formal que contiene reglas de producción recursivas.

Humor recursivo

Una página de Wikipedia recurrente

La recursión 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 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 del tipo:

Recursión, ver Recursión.

Se encuentra una variación en la página 269 del índice de algunas ediciones del libro The C Programming Language de Brian Kernighan y Dennis Ritchie; la entrada de índice hace referencia recursivamente 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 Herramientas de software de Kernighan y Plauger (publicado por Addison-Wesley Professional el 11 de enero de 1976). El chiste también aparece en El entorno de programación UNIX de Kernighan y Pike. No apareció en la primera edición de El lenguaje de programación C. El chiste forma 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." En la versión en inglés del motor de búsqueda web de Google, cuando se realiza una búsqueda de "recursión" se hace, el sitio sugiere "Quiso decir: recursividad." Una forma alternativa es la siguiente, de Andrew Plotkin: "Si ya sabe qué es la recursividad, simplemente recuerde la respuesta. De lo contrario, encuentre a alguien que esté más cerca de Douglas Hofstadter que usted; luego pregúntele qué es la recursividad."

Las siglas recursivas son otros ejemplos de humor recursivo. PHP, por ejemplo, significa "PHP Hypertext Preprocessor", WINE significa "WINE Is Not an Emulator" GNU significa "GNU's not Unix", y SPARQL denota "SPARQL Protocol and RDF Query Language".

En matemáticas

El triángulo Sierpinski: una recursión confinada de triángulos que forman un fractal

Conjuntos definidos recursivamente

Ejemplo: los números naturales

El ejemplo canónico de un conjunto definido recursivamente está dado por los números naturales:

0 está en ${displaystyle mathbb {N}$

si n está dentro ${displaystyle mathbb {N}$, entonces n + 1 está en ${displaystyle mathbb {N}$

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 refiriéndose 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 todos los "probables" proposiciones 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:

• Si una proposición es un axioma, es una proposición provable.
• Si una proposición puede derivarse de verdaderas proposiciones alcanzables por medio de reglas de inferencia, es una proposición provable.
• El conjunto de proposiciones provables es el conjunto más pequeño de proposiciones que satisfacen estas condiciones.

Reglas de subdivisión finita

Las reglas de subdivisión finita son una forma geométrica de recursividad 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 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. Los "tercios medios" estándar La técnica 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 recursivamente en términos de sí misma. Un ejemplo familiar es la secuencia numérica de Fibonacci: F(n) = F(n − 1) + < i>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.

Una función recursiva famosa es la función de Ackermann que, a diferencia de la sucesión de Fibonacci, no se puede expresar sin recursividad.

Pruebas que involucran definiciones recursivas

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

Optimización recursiva

La programación dinámica es un enfoque de la 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).

El teorema de recursión

En la teoría de conjuntos, este es un teorema que garantiza que existen funciones recurrentemente definidas. Dado un conjunto X, un elemento a de X y una función f: X → X, el teorema declara que hay una función única ${displaystyle F:mathbb {N}to X}$ (donde) ${displaystyle mathbb {N}$ denota el conjunto de números naturales incluyendo cero) tal que

${displaystyle F(0)=a}$

${displaystyle F(n+1)=f(F(n)}$

para cualquier número natural n.

Prueba de unicidad

Tomar dos funciones ${displaystyle F:mathbb {N}to X}$ y ${displaystyle G:mathbb {N} to X}$ tal que:

${displaystyle F(0)=a}$

${displaystyle G(0)=a}$

${displaystyle F(n+1)=f(F(n)}$

${displaystyle G(n+1)=f(G(n)}$

donde a es un elemento de X.

Se puede probar por inducción matemática que F(n) = G( n) para todos los números naturales n:

Caso básico: F(0) a = G(0) por lo que la igualdad n = 0.

Paso inductivoSuppose F()k) G()k) para algunos ${displaystyle kin mathbb {N}$. Entonces... F()k + 1) f()F()k) = f()G()k) = G()k + 1).

Por lo tanto F()k) G()k) implicación F()k + 1) G()k + 1).

Por inducción, F()n) G()n) para todos ${displaystyle nin mathbb {N}$.

En informática

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. 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 recursividad es la definición de la función factorial, dada aquí en código C:

no firmado int factorial()no firmado int n) {} si ()n == 0) {} retorno 1; } más {} retorno n * factorial()n - 1); }}

La 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, análogamente 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. La solución al problema se idea luego combinando las soluciones obtenidas de las versiones más simples del problema. Un ejemplo de aplicación de recursión es en analizadores para 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 oraciones, diseños u otros datos posibles.

Las relaciones de recurrencia son ecuaciones que definen una o más secuencias recursivamente. 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 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 biología

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 parte grande se ramifica en dos o más partes similares más pequeñas. Un ejemplo es el brócoli romanesco.

En el arte

Muñecas Recursive: el conjunto original de muñecas Matryoshka por Zvyozdochkin y Malyutin, 1892

Cara frontal de Giotto Stefaneschi Triptych, 1320, repetitivamente contiene una imagen de sí misma (guardada por la figura de rodilla en el panel central).

La muñeca rusa o Matryoshka es un ejemplo físico artístico del concepto recursivo.

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. Esta práctica se conoce más generalmente como el efecto Droste, un ejemplo de la técnica Mise en abyme.

M. La Galería de grabados de C. Escher (1956) es un grabado que representa una ciudad distorsionada que contiene una galería que contiene recursivamente la imagen, y así ad infinitum.