Recursión - Recursion

Una forma visual de recursividad conocida como efecto Droste . La mujer de esta imagen sostiene un objeto que contiene una imagen más pequeña de ella sosteniendo un objeto idéntico, que a su vez contiene una imagen más pequeña de ella sosteniendo un objeto idéntico, y así sucesivamente. 1904 Lata de cacao Droste , diseñada por Jan Misset

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

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

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

Hay varias definiciones más irónicas de la recursividad; ver humor recursivo .

Definición informal

Masa madre recién renovada , burbujeando a través de la fermentación : la receta requiere un poco de masa madre sobrante de la última vez que se hizo la misma receta.

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

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.

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 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. 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. En cualquier caso, se puede argumentar que la autorreferencia literaria es 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 las oraciones para crear nuevas oraciones, y también para los significados de las frases nominales, los significados 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.

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

Humor recursivo

Una página de Wikipedia recursiva

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 .

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 esta broma 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 11 de enero de 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 . La broma es parte del folclore de la programación funcional y ya estaba muy extendida 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 "recursividad", el sitio sugiere "Quiso decir: recursividad ". 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 recursión".

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

El triángulo de Sierpinski: una recursividad confinada de triángulos que forman un fractal

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

{\ Displaystyle \ mathbb {N}}

si n está en , entonces n + 1 está en

{\ Displaystyle \ mathbb {N}}

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

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 varios 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 \to X$ , el teorema establece que hay una función única (donde denota el conjunto de números naturales incluyendo el cero) tal que ${\ Displaystyle F: \ mathbb {N} \ to X}$ ${\ Displaystyle \ mathbb {N}}$

{\ Displaystyle F (0) = a}

{\ Displaystyle F (n + 1) = f (F (n))}

para cualquier número natural $n$ .

Prueba de singularidad

Tome dos funciones y tales que: ${\ Displaystyle F: \ mathbb {N} \ to X}$ ${\ Displaystyle G: \ mathbb {N} \ to X}$

{\ Displaystyle F (0) = a}

{\ Displaystyle G (0) = a}

{\ Displaystyle F (n + 1) = f (F (n))}

{\ Displaystyle G (n + 1) = f (G (n))}

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)

.

{\ Displaystyle k \ in \ mathbb {N}}

Por tanto,

F (k) = G (k)

implica

F (k + 1) = G (k + 1)

.

Por inducción, $F (n) = G (n)$ para todos . ${\ Displaystyle n \ in \ mathbb {N}}$

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. La solución al problema se concibe luego 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 .

En arte

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

Cara frontal de Giotto 's Stefaneschi Tríptico , 1320, contiene de forma recursiva una imagen de sí mismo (sostenido por la figura arrodillada en el panel central).

La muñeca rusa o la muñeca Matryoshka es un ejemplo artístico físico 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.

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 .

Ver también

Referencias

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.

Languages

In other projects